在 Javascript 中,如何检查数组是否有重复值?

2022-01-10 00:00:00 duplicates javascript

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

如何检查数组是否有重复值?

How do I check if an array has duplicate values?

如果数组中的某些元素相同,则返回true.否则,返回 false.

If some elements in the array are the same, then return true. Otherwise, return false.

['hello','goodbye','hey'] //return false because no duplicates exist
['hello','goodbye','hello'] // return true because duplicates exist

请注意,我不关心查找重复项,只需要布尔结果数组是否包含重复项.

Notice I don't care about finding the duplication, only want Boolean result whether arrays contains duplications.

推荐答案

如果你有一个 ES2015 环境(在写这篇文章时:io.js, IE11, Chrome, Firefox, WebKit nightly),那么下面的将起作用,并且会很快(即 O(n)):

If you have an ES2015 environment (as of this writing: io.js, IE11, Chrome, Firefox, WebKit nightly), then the following will work, and will be fast (viz. O(n)):

function hasDuplicates(array) {
    return (new Set(array)).size !== array.length;
}

<小时>

如果您只需要数组中的字符串值,则可以使用以下方法:


If you only need string values in the array, the following will work:

function hasDuplicates(array) {
    var valuesSoFar = Object.create(null);
    for (var i = 0; i < array.length; ++i) {
        var value = array[i];
        if (value in valuesSoFar) {
            return true;
        }
        valuesSoFar[value] = true;
    }
    return false;
}

我们使用哈希表"valuesSoFar,其键是我们目前在数组中看到的值.我们使用 in 进行查找以查看是否已经发现了该值;如果是这样,我们跳出循环并返回 true.

We use a "hash table" valuesSoFar whose keys are the values we've seen in the array so far. We do a lookup using in to see if that value has been spotted already; if so, we bail out of the loop and return true.

如果您需要的函数不仅仅适用于字符串值,则以下方法可以使用,但性能不佳;它是 O(n2) 而不是 O(n).

If you need a function that works for more than just string values, the following will work, but isn't as performant; it's O(n2) instead of O(n).

function hasDuplicates(array) {
    var valuesSoFar = [];
    for (var i = 0; i < array.length; ++i) {
        var value = array[i];
        if (valuesSoFar.indexOf(value) !== -1) {
            return true;
        }
        valuesSoFar.push(value);
    }
    return false;
}

不同之处在于我们对 valuesSoFar 使用数组而不是哈希表,因为 JavaScript 哈希表"(即对象)只有字符串键.这意味着我们失去了 in 的 O(1) 查找时间,而获得了 indexOf 的 O(n) 查找时间.

The difference is simply that we use an array instead of a hash table for valuesSoFar, since JavaScript "hash tables" (i.e. objects) only have string keys. This means we lose the O(1) lookup time of in, instead getting an O(n) lookup time of indexOf.

相关文章