javascript - 用 for 循环修改函数以提高效率

Question

我正在创建一个从数组参数返回唯一整数的函数。我写了一个可以工作的函数，但它太慢了。该函数通过所有逻辑测试但超时。

函数接受这样的参数:

[9,2,1,2,1,6,1,1,6,2,8,1,8]

我的函数:

function findUnique(numbers) {

        let unqNumber, matchCount,i,y;
        let len = numbers.length;

        for (i = 0; i < len; i++  ) {
                matchCount = 0;
                for (y = 0; y < len; y++ ) {
                        if (numbers[i] == numbers[y]) {
                                matchCount++;                           
                        }               
                }
                if (matchCount == 1) {
                        unqNumber = numbers[i]
                }
        }
        return unqNumber;
}

它将每个索引与所有其他索引进行比较并计算出现次数。只出现1次的索引是唯一编号。

传入的数组中始终只有一个唯一数字。

我知道 for 循环效率低下，但我不知道另一种写法。我可以使用 filter() 或 map() 来更快更有效地完成这项工作吗？

Answer 1

使用 HashMap 。当前代码的复杂度为 O(n*n)。使用 hashmap，它将是 O(n)。

例如)

var temp = [9,2,1,2,1,6,1,1,6,2,8,1,8];

function findUnique(numbers) 
{
    let unqNumber,i;
    let len = numbers.length;

    var mymap = {};
    for(i = 0; i < len; i++)
    {
        if(numbers[i] in mymap)
        {
            mymap[numbers[i]]++;
        }
        else
        {
            mymap[numbers[i]] = 1;
        }
    }
    console.log(mymap);
    //{1: 5, 2: 3, 6: 2, 8: 2, 9: 1}
    for(var j in mymap) 
    {
        if(mymap[j] == 1)
        {
            unqNumber = j;
        }
    }
    return unqNumber;
}

console.log(findUnique(temp));
//9