题目链接：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.

Hint:

Could you do it in-place with O(1) extra space?

这道题的要求是将数组向右旋转k步。

可以开一个数组存储要旋转出来的元素，不过这样空间复杂度不是O(1)。

接下来：

  1. Reverse

假设旋转数组1、2、3、4、5，k=2，那么旋转后为：4、5、1、2、3。可以将1、2、3看成向量a，4、5看成向量b，那么旋转ab就生成ba。这个过程，相当于现对a求逆，得到aTb，在对b求逆，得到aTbT，接着整体求逆，得到ba。

整理一下，全过程分为3部分：

  • 左部分反转
  • 右部分反转
  • 整体反转

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11

class Solution
{
public:
    void rotate(int nums[], int n, int k)
    {
        k %= n;
        reverse(nums, nums + (n - k));
        reverse(nums + (n - k), nums + n);
        reverse(nums, nums + n);
    }
};

  1. 逐个旋转处理

这里说一下常规思路，将最后一个元素nums[n-1]移到临时变量temp中，然后移动nums[n-1-k]到nums[n-1]，移动nums[n-1-2k]到nums[n-1-k]，依此类推，直到返回到元素nums[n-1]结束。假设旋转数组1、2、3、4，k=2，那么：

  • temp = nums[3], nums[3] = nums[1], nums[1] = temp
  • temp = nums[2], nums[2] = nums[0], nums[0] = temp

这样只需加个计数器cnt用于统计移动了多少个元素，直到cnt等于n结束。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution
{
public:
    void rotate(int nums[], int n, int k)
    {
        k %= n;
        
        int cnt = 0;
        for(int i = n - 1; cnt < n; -- i, ++ cnt)
        {
            int temp = nums[i], cur = i, front = (cur + n - k) % n;
            while(front != i)
            {
                nums[cur] = nums[front];
                cur = front;
                front = (cur + n - k) % n;
                ++ cnt;
            }
            nums[cur] = temp;
        }
    }
};

其实，外层循环的次数就是n和k的最大公约数。用近世代数术语来说，就是旋转产生的置换群的陪集个数。————出自《编程珠玑》

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution
{
public:
    void rotate(int nums[], int n, int k)
    {
        k %= n;
        if(k == 0)
            return ;
        
        int gcd_n_k = gcd(n, k);
        for(int i = n - 1; i > n - 1 - gcd_n_k; -- i)
        {
            int temp = nums[i], cur = i, front = (cur + n - k) % n;
            while(front != i)
            {
                nums[cur] = nums[front];
                cur = front;
                front = (cur + n - k) % n;
            }
            nums[cur] = temp;
        }
    }
private:
    int gcd(int i, int j)
    {
        while(i != j)
            i > j ? i -= j : j -= i;
        return i;
    }
};

  1. Swap子数组

这部分程序来自Gries的Sciences of Programming一书的18.1节。————出自《编程珠玑》

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution
{
public:
    void rotate(int nums[], int n, int k)
    {
        k %= n;
        if(k == 0)
            return;
            
        k = n - k;
        int i = k, j = n - k;
        while(i != j)
        {
            if(i > j)
            {
                swaps(nums + (k - i), nums + k, j);
                i -= j;
            }
            else
            {
                swaps(nums + (k - i), nums + (k + j - i), i);
                j -= i;
            }
        }
        swaps(nums + (k - i), nums + k, j);
    }
private:
    void swaps(int *a, int *b, int m)
    {
        while(m --)
            swap(*a ++, *b ++);
    }
};

  1. 不断Swap最后k个元素

不断将最后k个元素与前面k个元素交换，这样可以保证前面k个元素是旋转后的了。

接下来数组从k位置开始，同时更新n为n-k，k为k%n。

假设旋转数组1、2、3、4、5，k=3，那么：

  • 第一次swap后：3、4、5、2、1，前面3个元素以及排好序。接下来数组从元素2开始，n更新为2，k更新为1；
  • 第二次swap后：1、2，前面1个元素以及排好序。接下来数组从元素2开始，n更新为1，k更新为0；

由于k得0循环结束。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10

class Solution
{
public:
    void rotate(int nums[], int n, int k)
    {
        for ( ; k %= n; n -= k, nums += k)
            for (int i = 0; i < k; ++ i)
                swap(nums[i], nums[n - k + i]);
    }
};