问题描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例:

1
2
3
4
5
6
输入: 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]

解决方案

方法一：循环移动

这是一个直观的解决方案，通过循环k次，每次将数组最后一个元素移到开头。不过leetcode上提交超时了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function rotate1(nums, k) {
    if (k % nums.length === 0) {
        return
    }
    let n = nums.length
    for (let i = 0; i < k; i++) {
        let temp = nums[n - 1]
        for (let j = n - 2; j >= 0; j--) {
            nums[j + 1] = nums[j]
        }
        nums[0] = temp
    }
    return nums
}

算法分析：

  • 时间复杂度：O(n * k)，其中 n 是数组长度
  • 空间复杂度：O(1)，只使用了常数额外空间
  • 优点：代码直观，易于理解
  • 缺点：当数组较大且k较大时，效率较低

方法二：反转法

这是一个更优的解决方案，通过三次反转来完成旋转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function rotate(nums, k) {
    let n = nums.length
    k = k % n  // 处理 k > n 的情况
    reverse(nums, 0, n - 1)    // 先反转整个数组
    reverse(nums, 0, k - 1)    // 反转前k个元素
    reverse(nums, k, n - 1)    // 反转剩余元素
    return nums
}

function reverse(nums, start, end) {
    while (start < end) {
        [nums[start], nums[end]] = [nums[end], nums[start]]
        start++
        end--
    }
}

算法分析：

  • 时间复杂度：O(n)，只需要遍历一次数组
  • 空间复杂度：O(1)，原地操作
  • 优点：
    • 效率高，只需要遍历一次数组
    • 不需要额外空间
    • 适用于大数组和大k值的情况
  • 缺点：代码不如方法一直观

算法思路解释

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

  1. 第一次反转整个数组：[7,6,5,4,3,2,1]
  2. 反转前k个元素：[5,6,7,4,3,2,1]
  3. 反转剩余元素：[5,6,7,1,2,3,4]

总结

  1. 在处理数组旋转问题时，我们可以使用多种方法：

    • 循环移动：直观但效率较低
    • 反转法：效率高但不够直观

  2. 选择合适的算法需要考虑：

    • 时间复杂度
    • 空间复杂度
    • 数组大小
    • 旋转步数k的大小

  3. 实际应用中，建议使用反转法，因为它具有更好的时间复杂度和空间复杂度。

  4. 编程技巧：

    • 使用 k % n 处理k大于数组长度的情况
    • 使用解构赋值简化交换操作
    • 善用辅助函数提高代码可读性