循环运行不够快的 JavaScript 函数

Question

我正在尝试练习面试，并在网上发现了一个挑战，即编写一个函数，该函数将采用数字数组并仅返回数组中仅存在一次的值，并按顺序返回这些值。例如，数组 [1, 3, 5, 6, 1, 4, 3, 6] 应该返回 [4, 5]。

我有一个正在通过测试的脚本，但对于某些测试来说运行速度太慢。我这样做错了吗？有什么基本的方法可以加快速度吗？脚本以findTheNumbers开头，a为数组输入:

function findTheNumbers(a) {
    var retVal = [];
    var nonUnique = [];

    for (var i = 0; i < a.length; i++){
        var isUnique = true;
        if (i != 0){
            for (var j = 0; j < nonUnique.length; j++){
                if (a[i] == nonUnique[j]){
                    isUnique = false;
                    break;
                }
            }
        }

        if (isUnique){
            for (var k = 0; k < a.length; k++){
                if (a[i] == a[k] && i != k){
                    isUnique = false;
                    nonUnique.push(a[i]);
                    break;
                }
            }    
        }

        if (isUnique){
            retVal.push(a[i]);
            if (retVal.length == 2){
                break;
            }
        }


    }

    retVal = sortArrayOfLengthOfTwo(retVal);
    return retVal;
}

function sortArrayOfLengthOfTwo(array){
    var retVal = [];
    if (array[0] > array[1]){
        retVal.push(array[1]);
        retVal.push(array[0]);
    } else {
        retVal = array;
    }

    return retVal;
}

更新 -

不确定最好的地方在哪里，但这是我根据已接受答案的提示(运行速度更快)的新版本:

function findTheNumbers(a) {
    var retVal = [];
    var dict = {};
    for (var i = 0; i < a.length; i++){
        dict[a[i]] = 1 + (dict[a[i]] || 0);
    }

    for (var key in dict){
        if (dict[key] == 1){
            retVal.push(parseInt(key));
        }
    }

    return retVal;
}

Answer 1

当程序太慢时，经验法则是

• 首先归咎于你的算法
• 接下来归咎于您的实现(编辑:根据 Bergi 的建议)
• 最后归咎于语言

在你的例子中，你解析了整个数组n次，也就是说，复杂度是o(n^2)。您可以只使用一个完整的解析和每个元素的计数字典来执行相同的操作。

编辑您的新算法

你的新算法很好。为了您的采访，我有几点意见:

• 而不是var，您应该考虑尽可能多地使用const，否则让
• 毫不犹豫地将中间结果放入变量中
• 为变量使用更具描述性的名称

下面是我的实现方式:

function findTheUniqueNumbers(a) {
  const numberCounts = {} // I prefer "new Map()" on recent env.
  a.forEach( function(e) {
    const previousCount = numberCounts[e] || 0
    numberCounts[e] = previousCount + 1
  } )

  return Object.keys(numberCounts)
    .filter( function(e) {
      return numberCounts[e] === 1
    } )
}


const uniqueNumber = findTheUniqueNumbers([1, 3, 5, 6, 1, 4, 3, 6])
console.log(uniqueNumber)