javascript中的数组的unique()

Question

众所周知,没有内置函数可以在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不是只有框架和其他一些可能已经涵盖了这一点).

Answer 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讨论的任一库的方法将是您的最佳选择.

Answer 2

我认为当您的数组中有提供字符串表示形式的对象或函数（例如[Object object]. 因为你只能将字符串作为对象中的键（在此处的“哈希”对象中）。您需要循环到结果数组中以查找新条目是否已存在。它仍然比第一种方法更快。

Prototype JS 有一个“ uniq ”方法，你可能会从中得到启发。

Answer 3

充满乐趣（行动）

function uniqueNum(arr) {
    return Object.keys(arr.reduce(
        function(o, x) {o[x]=1; return o;}, {})).map(Number);
}