跳到主要内容

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 <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶：

  • 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

出处：LeetCode

解法一：额外数组​

思路​

我们可以使用一个额外的数组 copy 来存储原数组 nums 的元素。接着，我们可以将 copy 中的元素按照 (i + k) % n 的顺序放回到 nums 中，其中 n 是数组的长度。

代码​

function rotate(nums: number[], k: number): void {
  const n = nums.length;
  const copy = [...nums];
  for (let i = 0; i < n; i++) {
    nums[(i + k) % n] = copy[i];
  }
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是数组的长度。我们需要 O(n)O(n) 的时间来将数组 copy 中的元素放回到数组 nums 中。
  • 空间复杂度：O(n)O(n)，其中 nn 是数组的长度。我们需要 O(n)O(n) 的空间来存储数组 copy。

解法二：环状替换​

思路​

我们可以将数组中的所有元素向右移动 k 个位置，其中 k 可能大于数组的长度。我们可以先将 k 对数组长度 n 取模，得到实际需要移动的位置 k %= n。接着，我们可以将数组中的元素向右移动 k 个位置，即将数组中的第 i 个元素移动到 (i + k) % n 的位置。

我们可以先将整个数组反转，接着将前 k 个元素反转，最后将后 n - k 个元素反转。这样，我们就可以得到最终的结果。

代码​

function rotate(nums: number[], k: number): void {
  const n = nums.length;
  k %= n;
  reverse(nums, 0, n - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, n - 1);
}

function reverse(nums: number[], start: number, end: number): void {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是数组的长度。我们需要 O(n)O(n) 的时间来将数组中的元素反转。
  • 空间复杂度：O(1)O(1)。