当前位置：首页 > article >正文

轮转数组解决方法

article 2024/10/19 23:39:55

轮转数组

问题描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。也就是说，将数组的每个元素向右移动 k 个位置，超过数组长度的部分循环到数组的开头。

示例：

输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]

方法一：使用额外的数组

思路

创建一个与原数组大小相同的额外数组。
将原数组的元素按照旋转后的索引位置放入新数组中。
将新数组的值复制回原数组。

图解

假设 nums = [1,2,3,4,5,6,7], k = 3。

计算新位置：对于每个索引 i，新位置为 (i + k) % n，其中 n 是数组长度。

原索引 `i`	原元素 `nums[i]`	新索引 `(i + k) % n`	放入位置
0	1	(0 + 3) % 7 = 3	3
1	2	(1 + 3) % 7 = 4	4
2	3	(2 + 3) % 7 = 5	5
3	4	(3 + 3) % 7 = 6	6
4	5	(4 + 3) % 7 = 0	0
5	6	(5 + 3) % 7 = 1	1
6	7	(6 + 3) % 7 = 2	2

新数组为 [5,6,7,1,2,3,4]。

实现代码

function rotateUsingExtraArray(nums: number[], k: number): void {
    const n = nums.length;
    k = k % n; // 如果 k 大于数组长度，取模
    const rotatedArray = new Array(n);

    // 将旋转后的元素放入新数组
    for (let i = 0; i < n; i++) {
        rotatedArray[(i + k) % n] = nums[i];
    }

    // 将新数组的值复制回原数组
    for (let i = 0; i < n; i++) {
        nums[i] = rotatedArray[i];
    }
}

复杂度分析

时间复杂度：O(n)，需要遍历数组两次。
空间复杂度：O(n)，需要额外的数组存储旋转后的结果。

方法二：使用数组反转

思路

通过反转数组的部分或全部来实现旋转。
具体步骤：
1. 反转整个数组。
2. 反转前 k 个元素。
3. 反转剩余的元素。

图解

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

反转整个数组：

[1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
反转前 k 个元素：

[7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]
反转剩余的元素：

[5,6,7,4,3,2,1] → [5,6,7,1,2,3,4]

实现代码

function rotateUsingReverse(nums: number[], k: number): void {
    const n = nums.length;
    k = k % n; // 如果 k 大于数组长度，取模

    // 定义反转函数
    function reverse(start: number, end: number): void {
        while (start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]]; // 交换元素
            start++;
            end--;
        }
    }

    // 反转整个数组
    reverse(0, n - 1);
    // 反转前 k 个元素
    reverse(0, k - 1);
    // 反转剩余的元素
    reverse(k, n - 1);
}

复杂度分析

时间复杂度：O(n)，反转操作需要遍历数组三次，每次都是 O(n)。
空间复杂度：O(1)，只使用了常数级别的额外空间。

解释

为什么这种方法有效？
- 反转整个数组后，原来的末尾 k 个元素移动到了数组的开头，但顺序是反的。
- 通过再次反转前 k 个元素，将它们的顺序调整过来。
- 同理，反转剩余的元素，也恢复它们的顺序。

方法三：使用循环替换（环状替换）

思路

直接将每个元素放到它最终的位置，但需要注意可能会覆盖尚未移动的元素。
通过循环替换元素，避免数据被覆盖。

实现步骤

初始化计数器 count = 0，记录已经移动的元素数量。
从索引 start = 0 开始，进行循环替换：
- 保存当前位置的值 prevValue。
- 计算下一个位置的索引 next = (current + k) % n。
- 将 prevValue 放到 next 位置，保存 nums[next] 为新的 prevValue。
- 更新 current = next。
- 增加 count，直到 count 等于数组长度 n，表示所有元素都已移动。
如果出现循环，需要从下一个位置开始新的循环。

注意

当数组长度和 k 的最大公约数不为 1 时，会出现循环，需要从下一个起始位置继续。

实现代码

function rotateUsingCyclicReplacement(nums: number[], k: number): void {
    const n = nums.length;
    k = k % n; // 如果 k 大于数组长度，取模
    let count = 0; // 记录已经移动的元素个数

    for (let start = 0; count < n; start++) {
        let current = start;
        let prevValue = nums[start];

        do {
            const next = (current + k) % n;
            const temp = nums[next];
            nums[next] = prevValue;
            prevValue = temp;
            current = next;
            count++;
        } while (start !== current);
    }
}

复杂度分析

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

解释

为什么需要 count？
- 因为可能会出现环状替换，一个循环无法覆盖所有元素，所以需要计数。
示例演示：
- 以 nums = [1,2,3,4,5,6], k = 2 为例。
- 第一轮循环：
  - start = 0，current = 0，prevValue = nums[0] = 1
  - next = (0 + 2) % 6 = 2
  - nums[2] 被替换为 1，prevValue 更新为 nums[2] 的原值 3
  - current 更新为 2，count = 1
  - 重复上述步骤，直到 current 回到 start。
- 第二轮循环：
  - start = 1，重复类似的过程。

总结

方法一适用于不考虑空间复杂度的情况，理解起来较为直观。
方法二通过数组反转，实现原地旋转，空间复杂度低，性能优良。
方法三在空间复杂度为 O(1) 的情况下，时间效率较高，但理解起来稍微复杂。

测试代码

你可以使用以下测试代码来验证上述方法的正确性：

function testRotateFunctions() {
    const testCases = [
        { nums: [1, 2, 3, 4, 5, 6, 7], k: 3, expected: [5, 6, 7, 1, 2, 3, 4] },
        { nums: [-1, -100, 3, 99], k: 2, expected: [3, 99, -1, -100] },
    ];

    for (const { nums, k, expected } of testCases) {
        const nums1 = nums.slice();
        rotateUsingExtraArray(nums1, k);
        console.assert(nums1.toString() === expected.toString(), `rotateUsingExtraArray failed for input ${nums}, k=${k}`);

        const nums2 = nums.slice();
        rotateUsingReverse(nums2, k);
        console.assert(nums2.toString() === expected.toString(), `rotateUsingReverse failed for input ${nums}, k=${k}`);

        const nums3 = nums.slice();
        rotateUsingCyclicReplacement(nums3, k);
        console.assert(nums3.toString() === expected.toString(), `rotateUsingCyclicReplacement failed for input ${nums}, k=${k}`);
    }

    console.log("All test cases passed!");
}

testRotateFunctions();