unique() 用于 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

所以我自己做了:

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).

推荐答案

使用对象字面量正是我会做的.很多 很多人在很多时间都错过了这种技术，而是选择了典型的数组遍历作为您展示的原始代码.唯一的优化是避免每次 arr.length 查找.除此之外，O(n) 与您获得的唯一性一样好，并且比原始 O(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

总结时间复杂度

  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.

这篇关于unique() 用于 javascript 中的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！