康瑞部落

Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 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;
    }
};

二次刷题（2015-08-06）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        if(len == 0){
            return;
        }
        k = k%len;
        reverse(nums, 0, len - k - 1);
        reverse(nums, len - k, len - 1);
        reverse(nums, 0, len - 1);
    }
    
    void reverse(vector<int>& nums, int i, int j){
        while(i<j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    
    void swap(vector<int>& nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
};