为何HackerRank最大排列问题中高迭代代码比字典实现更快？

我针对HackerRank的《Largest Permutation》问题写了两个JavaScript解决方案：方案A在多数测试用例中可行，但部分用例会超时；而我原本认为时间复杂度更高的方案B却没有超时。我原本分析方案A是O(n)，方案B是O(n²)，但实际运行结果和我的分析不符，想请教其中原因以及正确的算法复杂度。

方案A（我的解决方案） #

const indices = {}
arr.forEach((n,i) => {
    indices[n] = i
})

let count = 0

while(count < k){
    // swap to earliest index (count)
    const targetValue = arr.length - count
    const targetIndex = indices[targetValue]

    let tmp = arr[count]
   
    arr[count] = arr[targetIndex]
    arr[targetIndex] = tmp
    
    //update indices
    indices[targetValue] = count
    indices[tmp] = targetIndex
    
    count++
}

return arr

方案B（我认为应更慢但实际更快的替代方案） #

let n = arr.length 
for(var i = 0; i < n - 1; i++) {
    if( k > 0) {
        var max = i;
        for(var j = i + 1; j < n; j++){
            if(arr[j] > arr[max])
                max = j;
        }
        if(max != i) {
            var temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
            k--;
        }
    }
}

return arr

问题分析 #

1. 方案A的逻辑缺陷与超时原因
   方案A存在两个关键问题：

   • 未判断当前位置是否已为最大值：即使当前arr[count]已经是该位置应放置的最大值（等于targetValue），代码仍会执行无意义的自交换操作。
   • 循环次数未限制在数组长度内：当k远大于数组长度n时，循环会执行k次——但实际上最多n次交换就能得到完全降序的排列。多余的循环会执行大量无用操作，比如count >= n时，targetValue会小于1，而题目数组是1~n的排列，此时indices[targetValue]为undefined，不仅会触发错误，还会浪费大量时间在无意义的赋值上，这就是部分测试用例超时的核心原因。

   方案A的理论时间复杂度是O(n + k)，当k远大于n时，实际复杂度退化为O(k)，若k达到1e6级别，必然会超时。

2. 方案B的实际复杂度与未超时原因
   你认为方案B是O(n²)，但这只是最坏情况（k >= n时）的复杂度。实际运行中：

   • 当k较小时（比如k=5），方案B只会执行k次内层遍历，总操作次数为k*n，在n规模不大时完全不会超时。
   • 当k >= n时，最多执行n-1次交换后k会变为0，后续外层循环仅递增i，不会执行内层遍历，此时实际复杂度为O(n²)，但如果测试用例中这类极端情况较少，或n规模不大，就不会触发超时。
   • 方案B逻辑正确：仅在需要交换时操作，k减到0后立即停止核心操作，不会做无用功。

方案A的修复方向 #

要修复方案A，可在循环内增加判断：若当前位置已是最大值，直接跳过交换，不消耗k。修改后的代码如下：

const indices = {}
arr.forEach((n,i) => {
    indices[n] = i
})

let count = 0

while(count < arr.length && k > 0){
    const targetValue = arr.length - count
    if(arr[count] === targetValue){
        count++
        continue
    }
    const targetIndex = indices[targetValue]

    let tmp = arr[count]
   
    arr[count] = arr[targetIndex]
    arr[targetIndex] = tmp
    
    indices[targetValue] = count
    indices[tmp] = targetIndex
    
    count++
    k--
}

return arr

修改后的方案A时间复杂度为O(n)，且不会执行无用操作，能有效避免超时。

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