【Leetcode hot 100】189.轮转数组

问题链接

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:

输入：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(n)）和空间复杂度优（O(1)）的特点。以下是详细的思路和实现步骤：

方法思路

轮转数组的核心是将数组元素向右移动 k 个位置。直接移动元素会涉及大量的元素交换，效率较低。而三次反转的方法可以高效地实现这一目标，具体步骤如下：

1. 处理 k 的取值：由于数组长度为 n 时，向右移动 n 个位置相当于没有移动，因此先对 k 取模（k = k % n），避免无效操作。
2. 反转整个数组：将原数组整体反转，使得末尾的 k 个元素移动到数组前面。
3. 反转前 k 个元素：将前 k 个元素反转，恢复它们的相对顺序。
4. 反转剩余元素：将剩下的 n-k 个元素反转，恢复它们的相对顺序。

解决代码

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return; // 处理空数组情况
        k %= n; // 取模，减少不必要的移动
        if (k == 0) return; // k为0时无需移动
        
        // 三次反转
        reverse(nums, 0, n - 1);    // 反转整个数组
        reverse(nums, 0, k - 1);    // 反转前k个元素
        reverse(nums, k, n - 1);    // 反转剩余的n-k个元素
    }
    
    // 辅助函数：反转数组从start到end的部分
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            // 交换首尾元素
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

代码解释

1. 处理边界情况：首先判断数组是否为空（n == 0），或 k 取模后为0（k == 0），此时无需移动，直接返回。
2. 取模操作：通过 k %= n 确保 k 在有效范围内（0 ≤ k < n），避免重复移动。
3. 三次反转：
   • 第一次反转：将整个数组反转，使末尾的 k 个元素移动到数组前端。
   • 第二次反转：反转前 k 个元素，恢复它们的相对顺序。
   • 第三次反转：反转剩余的 n-k 个元素，恢复它们的相对顺序。
4. 辅助函数 reverse：通过双指针法交换数组首尾元素，实现局部反转，时间复杂度为 O(n)。

这种方法高效且空间复杂度低，适合处理大规模数组。