javascript中数组的unique（）

一尘不染

javascript中数组的unique（）

algorithm

众所周知，没有内置函数可以从javascript中的数组中删除重复项。我注意到jQuery也缺少此功能（它仅具有用于DOM选择的独特功能），而我发现的最常见的代码段会检查整个数组以及每个元素的子集（我认为效率不高），例如：

for (var i = 0; i < arr.length; i++)
    for (var j = i + 1; j < arr.length; j++)
        if (arr[i] === arr[j])
            //whatever

所以我做了自己的：

function unique (arr) {
    var hash = {}, result = [];
    for (var i = 0; i < arr.length; i++)
        if (!(arr[i] in hash)) { //it works with objects! in FF, at least
            hash[arr[i]] = true;
            result.push(arr[i]);
        }
    return result;
}

我想知道是否有任何其他算法可以接受这种情况的最佳选择（或者您是否看到任何明显的缺陷可以解决），或者在javascript中需要此算法时会怎么做（我知道jQuery不是仅框架和其他框架可能已经涵盖）。

阅读 936

2020-07-28

共1个答案

一尘不染

使用对象字面量正是我要做的。很多人错过这个技术 有很多
的时间，转而选择典型的阵列散步的原始代码，您呈现。唯一的优化是避免arr.length每次查找。除此之外，O（n）与唯一性一样好，并且比原始O（n ^2）示例要好得多。

function unique(arr) {
    var hash = {}, result = [];
    for ( var i = 0, l = arr.length; i < l; ++i ) {
        if ( !hash.hasOwnProperty(arr[i]) ) { //it works with objects! in FF, at least
            hash[ arr[i] ] = true;
            result.push(arr[i]);
        }
    }
    return result;
}

// * Edited to use hasOwnProperty per comments

总结时间复杂度

  f()    | unsorted | sorted | objects | scalar | library
____________________________________________________________
unique   |   O(n)   |  O(n)  |   no    |  yes   |    n/a
original |  O(n^2)  | O(n^2) |   yes   |  yes   |    n/a
uniq     |  O(n^2)  |  O(n)  |   yes   |  yes   | Prototype
_.uniq   |  O(n^2)  |  O(n)  |   yes   |  yes   | Underscore

与大多数算法一样，需要权衡取舍。如果仅排序标量值，则对原始算法的修改将提供最佳解决方案。但是，如果您需要对非标量值进行排序，那么使用或模仿所uniq讨论的任何一种库的方法将是您的最佳选择。

2020-07-28