Four utility methods for js array deduplication

One question that must be prepared for the interview front end is how to remove duplicates of Javascript Array. As far as I know, baidu, tencent, shanda and so on have given this topic in the interview. This seems like a simple question, but it's actually a killer. Not only will you be tested to implement this function, but you will also be tested to see how well you understand the execution of computer programs.

I came up with a total of three algorithms to achieve this goal:

Array.prototype.unique1 = function()
{
var n = []; //A new temporary array
for(var i = 0; i < this.length; i++) //Traverses the current array
{
//If the ith of the current array is already stored in a temporary array, skip,
//Otherwise, push the current item into the temporary array
if (n.indexOf(this[i]) == -1) n.push(this[i]);
}
return n;
}

Array.prototype.unique2 = function()
{
var n = {},r=[]; //N is the hash table and r is the temporary array
for(var i = 0; i < this.length; i++) //Traverses the current array
{
if (!n[this[i]]) //If there is no current item in the hash table
{
n[this[i]] = true; //Deposited in the hash table
r.push(this[i]); //Push the current item of the current array into the temporary array
}
}
return r;
}

Array.prototype.unique3 = function()
{
var n = [this[0]]; //The result array
for(var i = 1; i < this.length; i++) //Let's start with the second term
{
//If the ith term of the current array does not first appear in the current array at the position of I,
// So that means that i The terms are repeating, ignore them. Otherwise the deposit The result array
if (this.indexOf(this[i]) == i) n.push(this[i]);
}
return n;
}

The first and third methods both use the indexOf method of array. The purpose of this method is to find where the stored parameter first appears in the array. Obviously, the js engine implements this method by iterating through the groups until it finds the target. So this function wastes a lot of time. The second method USES a hash table. Store an object that has already appeared in the form of a subscript. Subscript references are much faster than using indexOf to search an array.

To determine the efficiency of these three methods, I ran a test program that generated an array of 10,000 random Numbers and tested the execution time using several methods. The results show that the second method is much faster than the other two methods. But the memory footprint should be more the second way, because there is an extra hash table. This is called space time. This is the test page, and you can check it out.

I wrote the fourth method:

Array.prototype.unique4 = function()
{
this.sort();
var re=[this[0]];
for(var i = 1; i < this.length; i++)
{
if( this[i] !== re[re.length-1])
{
re.push(this[i]);
}
}
return re;
}

The idea is to sort the array and then compare two adjacent values. Sort when using JS native sort method, JS engine should be used to sort quickly. The end result is that this method runs on average about three times as long as the second method, but much faster than the first and third methods.