如何优化通过交换实现连续整数升序排列的JavaScript函数效率？

问题根源分析 #

你当前的代码看起来只有一层循环，但arr.indexOf(i+1)方法底层会遍历整个数组查找目标值，单次操作时间复杂度为O(n)，因此整体时间复杂度是O(n²)。当输入规模达到100000时，运算量会达到10^10次，远超JS在10秒内可处理的运算上限，因此会触发超时。

优化方案1：基于原逻辑新增索引映射（时间复杂度O(n)，空间复杂度O(n)） #

我们可以提前构建一个「值→索引」的映射表，后续查找目标值位置直接从表中取值，不需要每次遍历数组，交换元素时同步更新映射表保证数据准确即可，优化后代码如下：

function minimumSwaps(arr) {
    let swaps = 0;
    const len = arr.length;
    // 因为元素是1~n的连续整数，用数组当哈希表效率更高
    const valueToIndex = new Array(len + 1);
    for (let i = 0; i < len; i++) {
        valueToIndex[arr[i]] = i;
    }

    for (let i = 0; i < len; i++) {
        const target = i + 1;
        if (arr[i] !== target) {
            // O(1)开销获取目标值索引
            const targetIndex = valueToIndex[target];
            const currentVal = arr[i];
            // 交换元素
            arr[i] = target;
            arr[targetIndex] = currentVal;
            // 更新被交换元素的索引映射
            valueToIndex[currentVal] = targetIndex;
            swaps++;
        }
    }
    return swaps;
}

优化方案2：循环节计数法（时间复杂度O(n)，空间复杂度O(n)） #

这是求排列最小交换次数的经典算法：将数组视为一个排列，每个元素指向它应该放置的位置，会形成若干闭合循环。长度为k的循环仅需要k-1次交换即可让所有元素归位，累加所有循环的k-1值就是最终最小交换次数，代码如下：

function minimumSwaps(arr) {
    let swaps = 0;
    const len = arr.length;
    const visited = new Array(len).fill(false);

    for (let i = 0; i < len; i++) {
        // 已访问过或元素已在正确位置则跳过
        if (visited[i] || arr[i] === i + 1) continue;
        let cycleLength = 0;
        let current = i;
        // 遍历当前循环节
        while (!visited[current]) {
            visited[current] = true;
            // 跳转到当前元素应该所在的位置
            current = arr[current] - 1;
            cycleLength++;
        }
        swaps += cycleLength - 1;
    }
    return swaps;
}

以上两种方案处理100000规模的输入都可以在毫秒级完成，不会触发超时限制。

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