旋转数组

题目：

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例：

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

思路一：

临时数组存储最后k个元素，原数组前n-k个元素移动到尾部，再从临时数组把数据移到原数组首部。

思路二：

数组翻转。先翻转全部数组，然后翻转前k个元素，最后翻转后n-k个元素。

代码一（临时数组）：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n <= 1)
            return;

        k = k%n;
        if(k == 0)
            return;

        vector<int> tmp;
        for(int i=n-k; i<n; i++)
        {
           tmp.push_back(nums[i]);
        }

        for(int i=n-k-1; i>=0; i--)
        {
            nums[i+k] = nums[i];
        }

        for(int i=0; i<k; i++)
            nums[i] = tmp[i];
    }
};

代码二（数组翻转）：

class Solution {
public:
    void reverse(vector<int>& nums, int begin, int end)
    {
        while(begin < end)
        {
            swap(nums[begin], nums[end]);
            begin++;
            end--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n <= 1)
            return;

        k = k%n;
        if(k == 0)
            return;

        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }
};