Best way to return duplicate elements in an array

Question

This is how I use to return duplicate elements. But I ran into the most dangerous performance issues, such as closing the browser, etc., when my array has a large number of elements with long texts.

var arr = [9, 9, 111, 2, 3, 4, 4, 5, 7]; var sorted_arr = arr.sort(); var results = []; for (var i = 0; i < arr.length - 1; i++) { if (sorted_arr[i + 1] == sorted_arr[i]) { results.push(sorted_arr[i]); } } alert(results); 

Please suggest me the best way to do this.

Answer 1

I do not get exactly what you want, but if you need to return duplicates, you can use the cache object. it works with a number or a string or something else.

 var arr = [9, 9, 111, 2, 3, 4, 4, 5, 7]; var cache = {}; var results = []; for (var i = 0, len = arr.length; i < len; i++) { if(cache[arr[i]] === true){ results.push(arr[i]); }else{ cache[arr[i]] = true; } } console.log(results);//returns an array with 9 and 4 

Of course, you can do other things, such as deleting multiple items, etc. etc.

EDIT - I wrote a blog post on how to remove duplicates from an array

Answer 2

If you have an array filter, you also have indexOf and lastIndexOf, and you can return duplicates without sorting.

 var results, arr= [9, 9, 111, 2, 3, 4, 4, 5, 4, 7]; if(arr.filter){ results= arr.filter(function(itm, i){ return arr.lastIndexOf(itm)== i && arr.indexOf(itm)!= i; }); } else// use your loop method alert(results) /* returned value: (Array) 9,4 */ 

Answer 3

Assuming the Nicola solution doesn't work for you (since it uses about the same amount of memory as the original solution: two elements are stored for each element in the input, in the worst case), you can use the slower process of repeatedly searching for your input.

This requires the Array.indexOf method from ECMAScript 5. It has many browsers. For alternatives, see How to check if an array contains an object in JavaScript? .

 var arr = [9, 9, 111, 2, 3, 4, 4, 5, 7]; var results = []; for (var i = 0, len = arr.length - 1; i < len; i++) { if((results.indexOf(arr[i]) == -1) && (arr.indexOf(arr[i], i + 1) != -1)) { results.push(arr[i]); } } console.log(results); 

It uses no more memory than the input arr plus the output results , but it is an O (N ^ 2) algorithm and does not need to change arr .

Answer 4

Your method relies on sorting, which may or may not be one of the reasons why you have run out of space / time.

The canonical way to remove duplicates is to save the key hash map (object in JS). The keys of the objects you receive will not necessarily be in the order you want; you do not indicate whether you want to organize the results as well, but they are now.

You can null from the original array, since you no longer require it; when he gets the engine assembled before JS though.

You can remove duplicates “in place” by storing the “current index” in the sorted array and increasing it only when you move the non-duplicated element “down” from the counter index, and then crop the returned array.

The combination of the last two methods should mean that in general you will only have one array with a valid reference.

Change the example. Setting length explicit, since .slice() creates a new array.

 var have = {}; var arr = [9, 9, 111, 2, 3, 4, 4, 5, 7]; arr = arr.sort(); for (var rIdx = 0, i = 0; i < arr.length; i++) { if (have[arr[i]]) { arr[rIdx++] = arr[i]; } else { have[arr[i]] = true; } } arr.length = rIdx; console.log(arr);