Possible Duplicate:
Easiest way to find duplicate values in a javascript array
How do I check if an array has duplicate values?
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.
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;
}
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
.
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;
}
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
.