Tao's Blog
0%

[Leetcode]189.Rotate Array

Posted on In Comment Counts:
2.5k 2 mins.

题目描述

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?

例子

例子 1

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

例子 2

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

解题思路

方法零

首先最容易想到的是暴力法（每次将所有元素后移一位（旋转一步），重复 k 次），以及使用额外数组的方法。代码比较简单就不放了，时空复杂度分别是：

暴力法：
时间复杂度： O(nk)
空间复杂度： O(1)

使用额外数组：
时间复杂度： O(n)
空间复杂度： O(n)

方法一

通过观察可以发现，数组旋转是有一定规律的。以第一个例子为例：

1
2
3
4
5
6
7
8
9
10
[1, 2, 3, 4, 5, 6, 7]， k = 3

// 从头到尾翻转一次
[7, 6, 5, 4, 3, 2, 1]

// 0 到 k - 1 翻转
[5, 6, 7, 4, 3, 2, 1]

// k - 1 到 末尾翻转
[5, 6, 7, 1, 2, 3, 4]

发现了这个特点之后代码就非常简单了, 注意对 k 首先要对数组长度取模：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.size() <= 1) {
            return;
        }

        k %= nums.size();

        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }

private:
    void reverse(vector<int>& nums, int front, int back) {
        while (front < back) {
            swap(nums[front++], nums[back--]);
        }
    }
};

时间复杂度： O(n)
空间复杂度： O(1)

方法二

第一种方法比较取巧，可能一下子不容易想到。第二种方法是对每一个元素直接找到它旋转后对应的位置，然后放到该位置。还是同一个例子：

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

对 1 而言，它的下标是 0，可以计算出旋转之后它的位置应该是（0 + 3） % 7 = 3，所以可以直接把它放在 3 的位置，把对应位置的元素移过来，再把该位置的元素放在正确位置上。这里注意的时候计算第二个元素的的位置的时候要使用他原来的下标而不是移过来之后的下标，直至移过来的元素已经是在正确的位置上。下面对例子一进行完整演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[1, 2, 3, 4, 5, 6, 7]， k = 3

// 第一步，对 1 操作， （0 + 3） % 7 = 3
[4, 2, 3, 1, 5, 6, 7]

// 对 4，原来的下标是3， (3 + 3) % 7 = 6
[7, 2, 3, 1, 5, 6, 4]

// 对 7，（6 + 3） % 7 = 2
[3, 2, 7, 1, 5, 6, 4]

// 对 3， (2 + 3) % 7 = 5
[6, 2, 7, 1, 5, 3, 4]

// 对 6， (5 + 3) % 7 = 1
[2, 6, 7, 1, 5, 3, 4]

// 对 2， (1 + 3) % 7 = 4
[5, 6, 7, 1, 2, 3, 4]

// 对 5， (4 + 3) % 7 = 0，就是现在的位置，结束

这里要注意一下，如果 n % k = 0, 实际上我们每次移动的时候只会在相隔k的元素里面反复跳转，意味着不会进行 n 次跳转就提前结束，这个时候我们对下一个位置进行重复操作，例如：

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

对 1 进行上述操作，只会在 1， 3， 5 之间跳转；这个时候我们要进入下一个位置，进行重复操作，即放置 2， 4， 6；然后进入下一个位置，这个时候发现下标为2 (i % 2) == 0，说明这个位置已经处理过了，可以停止，具体实现的时候只需要比较遍历过的数字和总数组长度即可，因为最后一定会遍历过 n 个元素。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.size() <= 1 || k % nums.size() == 0) {
            return;
        }

        k %= nums.size();

        int count = 0, index = 0;
        while (count < nums.size()) {
            int prev_index = index;
            int correct_index = (prev_index + k) % nums.size();
            while (correct_index != index) {
                count++;
                swap(nums[correct_index], nums[index]);
                prev_index = correct_index;
                correct_index = (prev_index + k) % nums.size();
            }
            count++;
            index++;
        }
    }
};

时间复杂度：O(n)
空间复杂度：O(1)