轮转数组

#leetcode #2024/08/05 #done

目录

• 1. 总结
• 2. 题目及理解
• 3. 解题思路
  • 3.1. 解法一：分割数组，然后再组合数组
  • 3.2. 解法二：反转法
  • 3.3. 解法三：使用额外的数组
• 4. 错误记录

1. 总结

• 思路一：分割数组，再合并数组
• 思路二：翻转整个数组 → 翻转前 k 个元素 → 翻转后 n-k 个元素
  • 注意需要处理 k 大于数组长度的情况
    • k %= n; 即可
• 思路三：通过创建一个新的数组来存储结果，从而实现数组的轮转

2. 题目及理解

3. 解题思路

3.1. 解法一：分割数组，然后再组合数组

/**  
 * @param {number[]} nums  
 * @param {number} k  
 * @return {void} Do not return anything, modify nums in-place instead.  
 */ 数组分割  
var rotate = function (nums, k) {  
    const n = nums.length;  
    // base 1: 处理 k 大于数组长度的情况  
    k %= n; 
    // base 2:  
    // 如果 k 为 0 或数组长度为 0 或 1，无需旋转  
    if (k === 0 || n <= 1) {  
        return;  
    }  
    const part1 = nums.slice(-k);  
    const part2 = nums.slice(0, n - k);  
    // 直接修改 nums 
    // nums.length = 0;  
    // nums = [...part1, ...part2];  
    
    // 直接修改原数组  
    // 从 0 到 n 删除 n 个元素，然后插入 part1 和 part2  
    nums.splice(0, n, ...part1, ...part2)  
  
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)（因为我们创建了两个临时数组 part1 和 part2）

[!danger] 注意上面的两个 base 条件

3.2. 解法二：反转法

假设我们有一个数组 [1, 2, 3, 4, 5, 6, 7]，需要向右旋转 3 步。

• 步骤 1：反转整个数组 [1, 2, 3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3, 2, 1]
  • 想象一下，我们把这个数组写在一条绳子上，然后把绳子翻转过来。
• 步骤 2：反转前 k 个元素（这里 k = 3 ）
  • [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
  • 想象我们把绳子的前3个元素（7, 6, 5）单独拿出来翻转。
• 步骤 3：反转剩余的元素 [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]
  • 我们把剩下的元素（4, 3, 2, 1）也翻转一下。
• 最终结果：[5, 6, 7, 1, 2, 3, 4]

这就是我们想要的结果！

为什么这个方法有效？

1. 第一次反转把整个数组颠倒，将“需要移动到前面的元素“放到了数组的开头，但顺序是反的。
2. 第二次反转纠正了这些元素的顺序。
3. 第三次反转则纠正了其余元素的顺序。

这个方法的巧妙之处在于：

• 它不需要额外的空间来存储元素。
• 每个元素只被移动了常数次，所以效率很高。
• 它可以处理各种不同的旋转步数，包括大于数组长度的情况。

1. **第一次**反转把整个数组颠倒，将"需要移动到前面的元素"放到了数组的开头，但顺序是反的。
2. **第二次**反转**纠正了**这些元素的顺序。
3. **第三次**反转则**纠正了**其余元素的顺序。

// 数组分割
var rotate = function (nums, k) {
  // base 1 : 处理 k 大于数组长度的情况
  k %= nums.length;

  // base 2 : 如果 k 为 0 或数组长度为 0 或 1，无需旋转
  if (k === 0 || nums.length <= 1) {
    return;
  }

  // 翻转 ① : 翻转整个数组
  reverse(nums, 0, nums.length - 1);
  // 翻转 ② : 翻转前 k 个元素
  reverse(nums, 0, k - 1);
  // 翻转 ③ : 翻转后 n - k 个元素
  reverse(nums, k, nums.length - 1);
};

/**
 * @description 翻转数组，从 start 到 end
 * */
function reverse(nums, start, end) {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

• 时间复杂度为 O(n)
• 空间复杂度为 O(1)
  • 直接在原数组上操作，不需要额外的空间（除了几个临时变量）。

[!danger] 能够处理所有边界情况，包括 k = 0 和数组长度为 0 或 1 的情况 和 k > 数组长度的情况

3.3. 解法三：使用额外的数组

通过创建一个新的数组来存储结果，从而实现数组的轮转

这里不展示代码了

4. 错误记录

[!danger] 解法一中： 在 JavaScript 中，当我们将一个数组作为参数传递给函数时，我们传递的是数组的引用。在函数内部，nums = [...part1, ...part2] 这行代码创建了一个新的数组并将 nums 变量指向这个新数组，但这并不会改变原始数组的内容。函数外部的原数组保持不变