轮转数组
#leetcode #2024/08/05
另外见 12. 算法/3. 刷题篇/2. LeetCode 热题 100 题/13. 轮转数组|13. 轮转数组
目录
题目及理解
解题思路
解法一：分割数组，然后再组合数组
/**
* @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 条件
解法二：反转法
假设我们有一个数组 [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]
这就是我们想要的结果！
为什么这个方法有效？
- 第一次反转把整个数组颠倒，将“需要移动到前面的元素“放到了数组的开头，但顺序是反的。
- 第二次反转纠正了这些元素的顺序。
- 第三次反转则纠正了其余元素的顺序。
这个方法的巧妙之处在于：
- 它不需要额外的空间来存储元素。
- 每个元素只被移动了常数次，所以效率很高。
- 它可以处理各种不同的旋转步数，包括大于数组长度的情况。
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
// 数组分割
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 > 数组长度的情况
解法三：使用额外的数组
通过创建一个新的数组来存储结果，从而实现数组的轮转
这里不展示代码了
错误记录
[!danger] 解法一中： 在 JavaScript 中，当我们将一个数组作为参数传递给函数时，我们传递的是数组的引用。在函数内部，
nums = [...part1, ...part2]这行代码创建了一个新的数组并将nums变量指向这个新数组，但这并不会改变原始数组的内容。函数外部的原数组保持不变