轮转数组 | 秋招知识库

思路讲解

看示例 1，我们要把 $[1, 2, 3, 4, 5, 6, 7]$ 变成 $[5, 6, 7, 1, 2, 3, 4]$ 。

把 $[5, 6, 7, 1, 2, 3, 4]$ 视作 $[5, 6, 7] + [1, 2, 3, 4]$ 。我们首先要保证 $[5, 6, 7]$ 在 $[1, 2, 3, 4]$ 前面，这可以通过反转 $[1, 2, 3, 4, 5, 6, 7]$ 得到。

反转后数组变成 $[7, 6, 5, 4, 3, 2, 1]$ ，即 $[7, 6, 5] + [4, 3, 2, 1]$ 。对比最终目标，只需把 $[7, 6, 5]$ 反转，把 $[4, 3, 2, 1]$ 反转，就得到了 $[5, 6, 7, 1, 2, 3, 4]$ 。

这用到了「负负得正」的想法：把一个子数组反转两次，子数组不变。

在第一次反转中，我们不仅反转了子数组 $[1, 2, 3, 4]$ 和 $[5, 6, 7]$ ，还交换了这两个子数组的位置。然后，把这两个子数组分别再反转一次，就抵消掉了反转，相当于我们只交换了 $[1, 2, 3, 4]$ 和 $[5, 6, 7]$ ，得到 $[5, 6, 7, 1, 2, 3, 4]$ 。

算法

这里假设 $0 \leq k < n$ ，对于 $k \geq n$ 的情况，可以转换成 $0 \leq k < n$ 的情况（证明见后文）。

设 $nums = A + B$ ，其中 $A$ 是 $nums$ 的前 $n - k$ 个数， $B$ 是后 $k$ 个数。在上例中， $A = [1, 2, 3, 4]$ ， $B = [5, 6, 7]$ 。

题目要求把 $A + B$ 变成 $B + A$ ，这可以用三次反转实现：

把 $nums = A + B$ 反转，我们得到了 $rev (B) + rev (A)$ ，其中 $rev (A)$ 表示数组 $A$ 反转后的结果。在上例中， $rev (B) + rev (A) = [7, 6, 5] + [4, 3, 2, 1]$ 。
单独反转 $rev (B)$ ，因为一个数组反转两次是不变的，所以 $rev (rev (B)) = B$ ，我们得到了 $B$ 。
单独反转 $rev (A)$ ，得到 $rev (rev (A)) = A$ 。
现在数组变成 $B + A$ 。在上例中， $B + A = [5, 6, 7] + [1, 2, 3, 4]$ ，这正是我们想要的结果。

Python 解法1C++ 解法1

python

# 注：请勿使用切片，会产生额外空间
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(i: int, j: int) -> None:
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        n = len(nums)
        k %= n  # 轮转 k 次等同于轮转 k % n 次
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size(); // 轮转 k 次等同于轮转 k % n 次
        ranges::reverse(nums);
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

C++ 解法3

cpp

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        auto reverse = [&](int i, int j) {
            while (i < j) {
                swap(nums[i++], nums[j--]);
            }
        };

        int n = nums.size();
        k %= n; // 轮转 k 次等同于轮转 k % n 次
        reverse(0, n - 1);
        reverse(0, k - 1);
        reverse(k, n - 1);
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 是 $nums$ 的长度。
空间复杂度： $O (1)$ 。

附：正确性证明

向右轮转 $k$ 个位置后，下标 $i$ 的元素移动到下标 $(i + k) mod n$ 上，其中 $n$ 是 $nums$ 的长度。

下面证明「三次反转法」的正确性。

假设 $0 \leq k < n$ ，也就是 $0 \leq k \leq n - 1$ ，分类讨论：

如果 $n - k \leq i \leq n - 1$ ，那么第一次反转（整个数组的反转）会把下标 $i$ 的元素交换到下标 $n - 1 - i$ 上（注意 $0 \leq n - 1 - i \leq k - 1$ ，在第二次反转的范围中），第二次反转会把下标 $n - 1 - i$ 的元素交换到下标 $k - 1 - (n - 1 - i) = i + k - n$ 上。根据 $n - k \leq i \leq n - 1$ 可得 $0 \leq i + k - n \leq k - 1$ ，所以 $i + k - n = (i + k) mod n$ ，符合题目要求。
如果 $0 \leq i \leq n - k - 1$ ，那么第一次反转（整个数组的反转）会把下标 $i$ 的元素交换到下标 $n - 1 - i$ 上（注意 $k \leq n - 1 - i \leq n - 1$ ，在第三次反转的范围中），第三次反转会把下标 $n - 1 - i$ 的元素交换到下标 $k + n - 1 - (n - 1 - i) = i + k$ 上（注*）。根据 $0 \leq i \leq n - k - 1$ 可得 $k \leq i + k \leq n - 1$ ，所以 $i + k = (i + k) mod n$ ，符合题目要求。

对于 $k \geq n$ 的情况，由于轮转 $n$ 次等同于没有轮转，轮转 $n + 1$ 等同于轮转 $1$ 次……依此类推，轮转 $k$ 次等同于轮转 $k mod n$ 次。由于 $0 \leq k mod n \leq n - 1$ ，所以 $k \geq n$ 的情况也是正确的。

综上所述，对于任意非负整数 $k$ ，按照图中三次反转的方法，可以把下标 $i$ 的元素移动到下标 $(i + k) mod n$ 上。

注：对于下标区间 $[L, R]$ 的反转，由于 $i = L$ 会反转到 $R$ ， $i = L + 1$ 会反转到 $R - 1$ ， $i = L + 2$ 会反转到 $R - 2$ ，依此类推，下标 $i$ 和反转后的位置 $j$ 满足 $i + j = L + R$ ，所以 $i$ 会反转到 $L + R - i$ 。

变形题

改成向左轮转 $k$ 个位置。
如果 $nums$ 是个二维数组呢？见 1260. 二维网格迁移。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

思路讲解 ​

算法 ​

复杂度分析 ​

附：正确性证明 ​

变形题 ​

分类题单 ​

思路讲解

算法

复杂度分析

附：正确性证明

变形题

分类题单