189.Rotate Array
解法一,空间复杂度O(n)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {

        int length = nums.size();
        
        if(k <= 0 || length <= 1)
            return;
        
        //copy vector nums
        vector<int> copy_nums;
        vector<int>::iterator it = copy_nums.begin();
        
        copy_nums.insert(it,nums.begin(),nums.end());
        
        for(int i = 0;i < length;i++)
            nums[(i+k)%length] = copy_nums[i];
            
    }
};

这种方法比较简单和清晰,例如要将1 2 3 4 5 6 7 向右移动3次,变成5 6 7 1 2 3 4,原有1最终的位置是(0+3)%7 =3,那么将nums[3] = 1,如果所在加上k超过vector长度则取余。

解法二:

class Solution {
public:
    void rotate(vector<int>& nums, int k) 
    {
        int n = nums.size(), start = 0;
        for (; k %= n; n -= k, start += k) {
            for (int i = 0; i < k; i++) {
                swap(nums[start + i], nums[start + n - k + i]);
            }
        }
    }
};

Rotate Array discussion

解法三:
空间复杂度O(1)

class Solution {
public:
    void reverse(vector<int>&sub_vec,int start,int end)
    {
        for(;start < end;start++,end--)
        {
            int temp = sub_vec[start];
            sub_vec[start] = sub_vec[end];
            sub_vec[end] = temp;
        }
    }
    
    void rotate(vector<int>& nums, int k) {
        
        int length = nums.size();
        
        int circle = k % length;
        
        if(length <= 1 || circle == 0)
            return;
        
        reverse(nums,0,length-1);
        reverse(nums,0,circle-1);
        reverse(nums,circle,length-1);

            
    }
};

这个解法比较清晰和好理解:
假设a= {1,2,3,4,5,6,7}
k = 3.
第一次执行reverse之后我们得到如下数组:
{7,6,5,4,3,2,1}
第二次执行reverse我们得到如下数组:
{5,6,7,4,3,2,1}
第三次执行reverse我们得到如下数组:
{5,6,7,1,2,3,4}