LC189. 轮转数组 rotate-array

老马啸西风2025年10月10日大约 4 分钟

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

v1-暴力

思路

就直接用基础的方式，旋转多少次，执行多少次。

当然，可以预见的，大概率超时。

实现

class Solution {

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        
        for(int i = 0; i < k; i++) {
            // 旋转一圈
            int last = nums[n-1];

            for(int j = n-1; j > 0; j--) {
                nums[j] = nums[j-1];
            }

            nums[0] = last;
        }
    }

}

效果

超出时间限制
38 / 39 个通过的测试用例

复杂度

TC：O(n*k)

反思

暴力明显过于慢了。

v2-借助额外空间

思路

我们没必要一次次移动，可以一次移动 k 个位置。

比较简单的方法是借助额外的空间数组。

1）把对应的元素放置在新数组 (k+i) % n 的位置

2）直接复制回去

实现

class Solution {

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;

        int[] temps = new int[n];
        for(int i = 0; i < n; i++) {
            int ix = (k + i) % n;

            temps[ix] = nums[i];
        }

        // 覆盖到原始数组
        for(int i = 0; i < n; i++) {
            nums[i] = temps[i];
        }
    }

}

效果

2ms 击败 13.64%

复杂度

SC: O(n)

TC: O(n) 一次遍历，一次覆盖

反思

如何才能不用额外空间呢？

v3-环形替换（标准原地算法）

思路

i 位置的元素，新位置在 (k+i) % n。

但是没有额外空间会导致数据覆盖，怎么办呢？

其实可以借鉴 v1 的思路：

把一个元素搬到它的目标位置；

把目标位置原来的值临时保存，再搬到它自己的新位置；

这样周而复始，就形成了一个循环环（cycle）。

实现

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int count = 0; // 已移动的元素数量

        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];

            do {
                int next = (current + k) % n; // 目标位置
                int temp = nums[next];       // 暂存目标位置的值

                nums[next] = prev;           // 把 prev 放入目标位置
                prev = temp;                 // 更新 prev

                current = next;              // 前进
                count++;
            } while (start != current);
        }
    }
}

效果

2ms 13.64%

复杂度

TC: O(n)

SC: O(1)

反思

不过这个版本确实感觉难以记忆，容易写错。

v4-多次翻转

思路

原地移动，可以通过 reverse 神奇的实现。

以 nums = [1,2,3,4,5,6,7], k=3 为例：

步骤	操作	结果
Step1	整体反转	`[7,6,5,4,3,2,1]`
Step2	反转前 k=3 段	`[5,6,7,4,3,2,1]`
Step3	反转剩余部分	`[5,6,7,1,2,3,4]`

实现

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;

        //整体
        reverse(nums, 0, n-1);

        // 前 k
        reverse(nums, 0, k-1);

        // 剩余部分
        reverse(nums, k, n-1);
    }

    
    private void reverse(int[] nums, int left, int right) {
        while(left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            left++;
            right--;
        }
    }

}