Rotate Array

1，题目要求

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1: Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2: Input: [-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.Could you do it in-place with O(1) extra space?

给定一个数组，将数组向右旋转k步，其中k为非负数。

注意：

尝试提供尽可能多的解决方案，至少有3种不同的方法来解决这个问题。你可以在O（1）额外空间的情况下就地进行吗？

2，题目思路

对于这道题，要求将一个数组进行右旋。

这是一道非常经典的面试题，也有非常经典的解决办法。

方法一：开辟内存的解法 时间复杂度为O(n)，空间复杂度为O(n)，进行错位赋值即可，需要注意的是注意取余（这也是这种问题的关键点）

方法二：三次反转 因为STL自带逆转方法reverse，因此，我们只需要对前n-k个元素进行逆转，然后在对后k个元素进行逆转，最后再进行整体逆转，就可以得到最后的结果了。

方法三：依次交换 这种方法中，我们从一个元素，然后以k为跨度，“链式赋值”，当我们回到开始赋值的位置，说明我们完成了一圈的赋值，因此从开始位置的下一个位置再开始； 如果我们赋值的次数正好等于数组元素的个数，说明每一个元素都发生了右旋k步，算法也就结束了。 需要注意的是，这里使用了swap函数，是一个非常巧妙的方法，既实现了前一个赋值给当前元素的值，又实现了对当前元素的值的记录，以实现下一个等待右旋的值的保存。

3，代码实现

方法一：

int x = []() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); class Solution { public: void rotate(vector<int>& nums, int k) { vector<int> numCopy (nums.begin(),nums.end()); auto n = nums.size(); for(int i = 0;i < n;i++) nums[(i+k)%n] = numCopy[i]; } };

方法二：

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); k = k%n; reverse(nums.begin(), nums.begin()+n-k); reverse(nums.begin()+n-k, nums.end()); reverse(nums.begin(), nums.end()); } };

方法三：

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); int cnt = n; k = k%n; if(n <= 1 || k == 0) return; for(int i = k;cnt!=0;i++){ int j = i; int prev = nums[(i-k)%k]; while(cnt--!=0){ swap(prev, nums[j]); j = (j+k)%n; if(j == i) break; } } return; } };