A question that must be prepared for the front-end of the interview: How to remove duplicates of Javascript Array. As far as I know, Baidu, Tencent, Shanda and others have all posted this question in interviews. This question seems simple, but it actually contains murderous intent. What you test is not only about implementing this function, but also about your in-depth understanding of computer program execution.
I came up with three algorithms to achieve this:
Array.prototype.unique1 = function(){var n = []; //A new temporary array for(var i = 0; i < this.length; i++) //Transweep the current array {//If the i-th of the current array has been saved into the temporary array, then skip it, // 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 a hash table, and r is a temporary array for(var i = 0; i < this.length; i++) //Transipate through the current array {if (!n[this[i]]) //If there is no current item in the hash table {n[this[i]] = true; //Save 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]]; //Result array for(var i = 1; i < this.length; i++) //Transipate from the second item {//If the i-th item of the current array appears in the current array for the first time, //Then it means that the i-th item is repeated, ignore it. Otherwise, save 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 arrays. The purpose of this method is to find where the stored parameters first appear in the array. Obviously, when implementing this method, the js engine will iterate over the array until the target is found. So this function will waste a lot of time. The second method uses the hash table. Save the existing form of subscript into an object. The reference to the subscript is much faster than searching the array with indexOf.
In order to judge the efficiency of these three methods, I made a test program, generating an array of random numbers of 10,000 lengths, and then used several methods to test the execution time. The results show that the second method is much faster than the other two methods. However, there should be more second method in terms of memory usage, because there is an additional hash table. This is called changing time in space. This is the test page, you can also 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 of this method is to sort the array first and then compare two adjacent values. When sorting, you should use the JS native sort method. Quick sorting should be used inside the JS engine. The final test result is that the running time of this method is about three times that of the second method, but it is much faster than the first and third methods.