博文中会简要介绍Leetcode P0189题目分析及解题思路。

“Rotate Array”这道题本身比较简单，但是follow-up值得思考一下。这道题可以用多种方法来解决，比如循环k次得到数组（时间复杂度O(kn)，空间复杂度O(1)），直接加k取余得到最终轮转后的位置（时间复杂度O(n)，空间复杂度O(n)），也可以加k取余得到位置后循环移动时间复杂度O(n)，空间复杂度O(1)）。这三种方法都可以实现数组的轮转，这篇博文主要介绍后两种。

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

Follow up:

• 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并对N取余得到在结果数组中的下标，便可以实现轮转数组的要求。

以下是Java的题解代码实现。

class Solution {
    public void rotate(int[] nums, int k) {
        int N = nums.length;
        k = k%N;
        if (k == 0)
            return;
        
        int[] rotated = new int[N];
        for (int idx=0; idx<N; ++idx) {
            rotated[(idx+k)%N] = nums[idx];
        }
        
        System.arraycopy(rotated, 0, nums, 0, N)
    }
}

为了控制空间复杂度在O(1)，对于上述方法可以进行一些改进。首先我们来观察下述数组，

[1,2,3,4,5,6,7], k=3

对于第一个元素，将其移动到轮转后的位置，
[1,2,3,1,5,6,7], temp=4
此时中转站temp里存储了被1覆盖的元素4，然后我们再移动元素4到其轮转后的位置，
[1,2,3,1,5,6,4], temp=7
此时中转站temp里存储了被4覆盖的元素7，然后我们再移动元素7到其轮转后的位置，
[1,2,7,1,5,6,4], temp=3
...
以此类推即可。不难发现，只要在类似的轮转过程中没有出现中转站的元素将覆盖一个已经被轮转过的位置的这种情况，总是能够通过上述方法将所有元素都轮转。

但是除了上述情况，还有另一种情况，即中转站的元素将覆盖一个已经被轮转过的位置。我们可以观察如下数组，

[-1,-100,3,99], k=2

对于第一个元素，将其移动到轮转后的位置，
[-1,-100,-1,99], temp=3
此时中转站temp里存储了被-1覆盖的元素3，然后我们再移动元素3到其轮转后的位置，
[3,-100,-1,99], temp=-1
此时发现下一次轮转将覆盖已经被轮转过的位置，即-1的位置，也就是说本次轮转恰好轮转到了整个过程开始的起点。这时候需要将起点指针后移一位，然后重新开始轮转，
[3,-100,-1,-100], temp=99
...
以此类推即可。

以下是C++的题解代码实现。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int N = nums.size();
        k = k%N;
        if (k == 0)
            return;
        
        int count = 0, start = 0, temp = nums[0], idx = 0;
        while (count < N) {
            swap(temp, nums[(idx+k)%N]);
            idx = (idx+k)%N;
            ++count;
            
            if (idx == start && count < N) {
                ++start;
                idx = start;
                temp = nums[start];
            }
        }
    }
};