09-轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

方法一：使用额外数组

function rotate(nums: number[], k: number): void {const n = nums.length;k = k % n; // 处理 k 大于数组长度的情况const newNums = new Array(n).fill(0);for (let i = 0; i < n; i++) {newNums[(i + k) % n] = nums[i];}for (let i = 0; i < n; i++) {nums[i] = newNums[i];}
}// 示例调用
const nums1 = [1, 2, 3, 4, 5, 6, 7];
const k1 = 3;
rotate(nums1, k1);
console.log("轮转后的数组:", nums1);

复杂度分析

• 时间复杂度：O(n)，需要遍历数组两次。
• 空间复杂度：O(n)，创建了一个与原数组大小相同的新数组。

方法二：三次反转数组

先将整个数组反转，然后反转前 k 个元素，最后反转剩下的 n - k 个元素。

function reverse(nums: number[], start: number, end: number): void {while (start < end) {[nums[start], nums[end]] = [nums[end], nums[start]];start++;end--;}
}function rotate(nums: number[], k: number): void {const n = nums.length;k = k % n; // 处理 k 大于数组长度的情况reverse(nums, 0, n - 1);reverse(nums, 0, k - 1);reverse(nums, k, n - 1);
}// 示例调用
const nums2 = [1, 2, 3, 4, 5, 6, 7];
const k2 = 3;
rotate(nums2, k2);
console.log("轮转后的数组:", nums2);

复杂度分析

• 时间复杂度：O(n)，每个元素最多被反转两次。
• 空间复杂度：O(1)，只使用了常数级的额外空间。

方法三：环状替换

直接将元素放到它应该在的位置上，同时记录已经替换的元素数量，直到所有元素都被替换。

function rotate(nums: number[], k: number): void {const n = nums.length;k = k % n;let count = 0;for (let start = 0; count < n; start++) {let current = start;let prev = nums[start];do {const next = (current + k) % n;const temp = nums[next];nums[next] = prev;prev = temp;current = next;count++;} while (start!== current);}
}// 示例调用
const nums3 = [1, 2, 3, 4, 5, 6, 7];
const k3 = 3;
rotate(nums3, k3);
console.log("轮转后的数组:", nums3);

复杂度分析

• 时间复杂度：O(n)，每个元素只被移动一次。
• 空间复杂度：O(1)，只使用了常数级的额外空间。

综上所述，方法二和方法三在空间复杂度上更优，特别是方法二实现起来较为简洁，推荐使用。