0

可能重复：
在 JavaScript 数组中查找重复值的最简单方法

假设我有一个包含数千个元素的数组，并且

我想return true如果有2 个或更多元素具有相同的值。

我知道我可以运行 afor loop并检查每一对元素以找到答案。

但是有更快的方法吗？最好的方法是什么？

4

7 回答 7

1

对其进行排序（无论比较器如何），然后扫描。O(n log(n))。

于 2012-06-05T14:25:14.087 回答
1

这基本上是Element Distinctness Problem。您可以阅读它，但只有 1000 个元素，优化可能不值得。

如果您真的想优化它，您可以将元素推送到哈希表中并检查冲突是否重复。这将为您提供平均 O(n)（摊销），但在最坏的情况下为 O(n^2)。

于 2012-06-05T14:26:27.443 回答
0

可能最快的方法是使用本机方法。inArray不是其中之一。indexOf如果该方法不存在（旧浏览器），您可以使用并默认为 for 循环。

于 2012-06-05T14:26:34.043 回答
0

有一种更快的方法。它的具体实现取决于您在数组中的内容。但这个想法是下面的伪代码：

假设您有一个id(element)返回元素的字符串标识符的函数。

var map = {};

for(var i = 0; i < myArray.length; i++) {
    var currentId = id(myArray[i]);
    if(map.hasOwnProperty(id)) return true;
    map[id] = true;
}

这里的复杂性是线性的。

如果您没有自然 id，您可以从标识对象的属性构建一个，或者做一些更聪明的事情……您可以在这里做的最聪明的事情是重新实现哈希图。

于 2012-06-05T14:27:27.990 回答
0

试试这个：

Array.prototype.elementsNotDistinct = function () {
    var i, j, length = this.length - 1;

    for(i = 0; i < length; i++)
        for (j = i + 1; j <= length; j++)
            if (this[i] === this[j]) return true;

    return false;
};

然后，如果您有一个名为的数组，a您需要做的就是：

if (a.elementsNotDistinct()) {
    // do something
}
于 2012-06-05T14:31:53.933 回答
0

我认为Array内置indexOf操作会为您出色地工作（取决于您需要排序的数据）

// Filter out all instances that occur twice or more.

var example = [ 1, 2, 3, 3, 3, 5, 4, 3, 5, 3 ];
var result = Array.filter( function ( element ) {
    return this.indexOf( element ) >= 2;
}  
// result is an array of [3,5]

return result.length === 0;
于 2012-06-05T14:33:10.950 回答
0

您可以遍历数组并将对象键设置为等于数组中找到的元素（转换为字符串）。如果您的密钥已经存在，那么您在数组中找到了两个具有重复值的元素

function isAllDistinct() {
    var elements  = { },
        yourarray = [...];

    for (i=0, l=yourarray.length; i < l; i++) {
       var key = yourarray[i] + '';  // alternative to yourarray[i].toString()
       if (!elements[key]) {
         elements[key] = 1;
       }
       else {
         return false;
       }
    }
    return true;
}

复杂度：O(n)

于 2012-06-05T14:33:48.870 回答