189. 轮转数组

1. 题目简介

难度：中等，原题链接：189. 轮转数组。

给定一个整数数组 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. 问题分析

2.1 模拟算法

这道题最直接的解法是模拟：

1. 使用一个长度为 k 的临时数组保存最右边的 k 个数字
2. 将前 n - k 个数字右移
3. 将临时数组中的值赋给原数组的前 k 位

2.2 两次反转

但是我们看到题目最后有一个进阶的条件：

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

仔细观察题目中的测试用例 [1, 2, 3, 4, 5, 6, 7]，当 k = 3 时，输出结果为 [5, 6, 7, 1, 2, 3, 4]。

如果我们将输出数组的前 4 位和后 3 位分别反转，我们将得到 [7, 6, 5, 4, 3, 2, 1]，这是原始数组的反转。那么我们是否可以通过将原始数组局部反转，最后反转整个数组，来获得最后的输出呢？

对于题目中的用例，我们可以进行如下操作：

1. 考虑 k = 3，分别反转前 n - k 位与后 k 位，得到数组 [4, 3, 2, 1, 7, 6, 5]
2. 将上一步得到数组再次反转，得到最后的输出 [5, 6, 7, 1, 2, 3, 4]

我们也可以证明两次反转算法的正确性：

1. 对于数组中下标为 i 的元素，向右轮转 k 个位置，移动后的下标将为 i + k
2. 假设 i < n - k，反转 [0, n - k) 时，下标由 i 变成了 n - k - i
3. 再次对完整的数组进行翻转，上一步改变后的下标将变为 n - (n - k - i) = i + k，与 1 中得出的目标下标一致
4. 也可以自行证明 i >= n - k 时，反转后的下标依然与目标下标一致

3. 代码实现

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - k);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        int tmp = 0;
        while (start < end) {
            tmp = nums[start];
            nums[start++] = nums[--end];
            nums[end] = tmp;
        }
    }
}

4. 复杂度分析

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