LeetCode #189旋转数组：如何用暴力交换法正确实现？

这种循环交换的思路完全可以正确解决问题，但你的代码没处理多循环链的情况——当数组长度len和k的最大公约数（gcd）大于1时，数组会被分成多个独立的循环链，只从一个起始点出发没法遍历所有元素。

比如你提到的[1,2,3,4], k=2，数组长度4和k=2的最大公约数是2，所以存在两个独立循环链：0→2→0和1→3→1。你的代码从索引2出发，只能处理其中一个链，另一个链的元素根本没被修改，自然出问题。

修正后的代码 #

var rotate = function(nums, k) {
    const len = nums.length;
    k = k % len;
    if (k === 0) return; // 无需旋转直接返回

    // 计算最大公约数，确定需要处理的循环链数量
    const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
    const cycles = gcd(len, k);

    for (let start = 0; start < cycles; start++) {
        let currIndex = start;
        let currElement = nums[currIndex];
        let nextIndex;

        do {
            nextIndex = (currIndex + k) % len;
            const temp = nums[nextIndex];
            nums[nextIndex] = currElement;
            currElement = temp;
            currIndex = nextIndex;
        } while (currIndex !== start); // 回到起始点时结束当前循环链
    }
};

关键修正点 #

• k取模处理：当k大于数组长度时，旋转k步等价于旋转k%len步，避免无效操作。如果k取模后为0，直接返回即可。
• 计算循环链数量：通过最大公约数gcd(len, k)确定需要处理的起始点数量，每个起始点对应一个独立循环链。
• 逐个处理循环链：对每个起始点，循环交换直到回到起始位置，确保每个链上的元素都完成旋转。

内容的提问来源于stack exchange，提问作者whyguy