HappyLeetcode50:Rotate Array

浏览数：78 / 时间：2015年06月11日

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].

这道题虽然做了出来，但是显然不是最优解。显然空间要求没有达到。

有一点要尤为注意，在一开始的时候我就默认k是小于n的，实际上k可以大于n，所以在修改代码之后，我们所使用的k要对n取余。

我的思路是，把数组中前面的值先挪到后面去。后面的值在被替换之前先存进一个vector里面去，待前面的值安排完毕之后，把vector之中的数据取出，放在新数组的前面。

代码如下:

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        
        if (nums == NULL || n <= 0 )
            return;
        
        k = k%n;

        vector<int> TempSave;

        TempSave.reserve(k);
        int count = 0;//记录已经推进了多少个数据
        for (int i = n - k - 1; i >= 0; --i)
        {
            if (count < k){
                TempSave.push_back(nums[i + k]);
                count++;
            }

            nums[i + k] = nums[i];
        }

        int Temp = TempSave.size();
        if (TempSave.size() < k)
        {
            for (int i = k - 1; i >= Temp; --i)
                TempSave.push_back(nums[i]);
        }

        for (int i = 0; i < k; ++i)
        {
            nums[i] = TempSave.back();
            TempSave.pop_back();
        }    
    }
};

其实后来想想还是有更简单一些的方法，比如先把数组复制一遍，再根据情况裁剪出你需要的那一部分数组出来。

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        k = k % n;
        int* NewNums =new int[n * 2];
        for (int i = 0; i < n ; ++i)
        {
            NewNums[i] = nums[i];
            NewNums[i + n] = nums[i];
        }
        //int res = n - k;
        for (int i = 0; i < n; ++i)
        {
            nums[i] = NewNums[i + n - k];
        }
    }
};

代码量明显短了不少。