[LeetCode] Rotate Array

Rotate Array

Rotate an array ofnelements to the right byksteps.

For example, withn= 7 andk= 3, the array[1,2,3,4,5,6,7]is rotated to[5,6,7,1,2,3,4].

Note:Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

解题思路：

注意，这里的k是从后面还是数起，即例子中的k=3是指从7-3=4下标开始整体往前移动。且k可能大于n，因此需要k%=n。这里题目出的不是很明白。弄了我好久。

1、解法1。最naive的办法，申请一个等长的空间，，将n-k~n项存在前面，然后将0~n-k-1存在后面。最后拷贝到原数组上去。

class Solution {public:void rotate(int nums[], int n, int k) {if(n==0){return;}k %= n;int* d=new int[n];int dIndex = 0;for(int i = n – k; i < n; i++){d[dIndex++]=nums[i];}for(int i = 0; i < n – k; i++){d[dIndex++]=nums[i];}for(int i=0; i < n; i++){nums[i] = d[i];}delete[] d;}};2、解法2。旋转数组，相当于0~k旋转，k+1~n旋转，然后再将0~n旋转。因此可以得到下列代码：class Solution {public:void rotate(int nums[], int n, int k) {k %= n;reverse(nums, 0, n – 1);reverse(nums, 0, k – 1);reverse(nums, k, n – 1);}void reverse(int nums[], int start, int end){while(start < end){swap(nums, start, end);start++;end–;}}void swap(int nums[], int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}};3、解法3。这一种办法就没有这么容易理解了。但速度更快。具体看源代码。我也不甚明白。可以自己举个小例子跑一下。class Solution {public:void rotate(int nums[], int n, int k) {k %= n;int first = 0;int last = n;int middle = n – k;middle %= n;int next = middle;while(first!=next){swap(nums, first++, next++);if(next==last)next=middle;else if(first==middle)middle = next;}}void swap(int nums[], int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}};

困难是人的教科书。