唯一的（）在JavaScript数组 [英] unique() for arrays in javascript

问题描述

大家都知道有没有内置的函数从JavaScript中的数组删除重复。我注意到这也是在jQuery的缺乏（其中有一个独特的功能，只DOM选择），而最常见的片段，我发现检查整个阵列和它的每个元素的一个子集（不是很有效，我认为），像

As everybody knows there's no built-in function to remove the duplicates from an array in javascript. I've noticed this is also lacking in jQuery (which has a unique function for DOM selections only), and the most common snippet I found checks the entire array and a subset of it for each element (not very efficient I think), like:

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

所以我做我自己的：

so I made my own:

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是不是只有框架和一些其他人可能有这个已经覆盖）。

I wonder if there's any other algorithm accepted as the best for this case (or if you see any obvious flaw that could be fixed), or, what do you do when you need this in javascript (I'm aware that jQuery is not the only framework and some others may have this already covered).

推荐答案

使用对象字面正是我会怎么做。 很多的人错过这一技术的大量的时间的，转而选择典型的阵列散步的，你表现出原始的code。唯一的优化将是避免 arr.length 查找各一次。除此之外，O（n）是你得到的唯一性一样好，比原来的Ô要好得多（N ^ 2）的例子。

Using the object literal is exactly what I would do. A lot of people miss this technique a lot of the time, opting instead for typical array walks as the original code that you showed. The only optimization would be to avoid the arr.length lookup each time. Other than that, O(n) is about as good as you get for uniqueness and is much better than the original O(n^2) example.

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

时间复杂度总结

Time complexities to summarize

  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的的方法将是您最好的选择。

As with most algorithms, there are trade offs. If you are only sorting scalar values, you're modifications to the original algorithm give the most optimal solution. However, if you need to sort non-scalar values, then using or mimicking the uniq method of either of the libraries discussed would be your best choice.

这篇关于唯一的（）在JavaScript数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！