Eine Frage, auf die sich Front-End-Interviewer vorbereiten müssen: So entfernen Sie Duplikate aus dem Javascript-Array. Soweit ich weiß, haben Baidu, Tencent, Shanda usw. diese Frage alle in Interviews gestellt. Diese Frage scheint einfach, birgt aber tatsächlich versteckte Gefahren. Bei dem Test geht es nicht nur um die Realisierung dieser Funktion, sondern auch um Ihr tiefgreifendes Verständnis für die Ausführung von Computerprogrammen.
Um diesen Zweck zu erreichen, habe ich mir insgesamt drei Algorithmen ausgedacht:
Array.prototype.unique1 = function()
{
var n = []; //一个新的临时数组
for(var i = 0; i < this.length; i++) //遍历当前数组
{
//如果当前数组的第i已经保存进了临时数组，那么跳过，
//否则把当前项push到临时数组里面
if (n.indexOf(this[i]) == -1) n.push(this[i]);
}
return n;
}
Array.prototype.unique2 = function()
{
var n = {},r=[]; //n为hash表，r为临时数组
for(var i = 0; i < this.length; i++) //遍历当前数组
{
if (!n[this[i]]) //如果hash表中没有当前项
{
n[this[i]] = true; //存入hash表
r.push(this[i]); //把当前数组的当前项push到临时数组里面
}
}
return r;
}
Array.prototype.unique3 = function()
{
var n = [this[0]]; //结果数组
for(var i = 1; i < this.length; i++) //从第二项开始遍历
{
//如果当前数组的第i项在当前数组中第一次出现的位置不是i，
//那么表示第i项是重复的，忽略掉。否则存入结果数组
if (this.indexOf(this[i]) == i) n.push(this[i]);
}
return n;
}
Die erste und dritte Methode verwenden beide die indexOf-Methode des Arrays. Der Zweck dieser Methode besteht darin, das erste Vorkommen des gespeicherten Parameters im Array zu finden. Offensichtlich durchläuft die js-Engine bei der Implementierung dieser Methode das Array, bis sie das Ziel findet. Diese Funktion verschwendet also viel Zeit. Die zweite Methode verwendet eine Hash-Tabelle. Speichern Sie die Vorkommen in einem Objekt in Form von Indizes. Indizierte Referenzen sind viel schneller als das Durchsuchen des Arrays mit indexOf.
Um die Effizienz dieser drei Methoden zu beurteilen, habe ich ein Testprogramm erstellt, um ein Array von Zufallszahlen mit einer Länge von 10.000 zu generieren, und dann mehrere Methoden verwendet, um die Ausführungszeit zu testen. Die Ergebnisse zeigen, dass die zweite Methode viel schneller ist als die beiden anderen Methoden. Hinsichtlich der Speichernutzung dürfte jedoch eher die zweite Methode zum Einsatz kommen, da eine zusätzliche Hash-Tabelle vorhanden ist. Das nennt man Raum für Zeit. Dies ist die Testseite, Sie können sie sich auch ansehen.
Nach den Vorstellungen von HPL-Experten habe ich die vierte Methode geschrieben:
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;
}
Die Idee dieser Methode besteht darin, zuerst das Array zu sortieren und dann zwei benachbarte Werte zu vergleichen. Beim Sortieren wird die native JS-Sortiermethode verwendet. Die JS-Engine sollte intern die Schnellsortierung verwenden. Das endgültige Testergebnis ist, dass die Laufzeit dieser Methode im Durchschnitt etwa dreimal so hoch ist wie die der zweiten Methode, sie ist jedoch viel schneller als die erste und dritte Methode.
Die fünfte Methode
Ich habe kürzlich die Funktion [Suchverlauf] verwendet und begonnen, die Methode indexOf zu verwenden. Diese Methode wird nur in ECMA5, aber nicht in IE8 unterstützt.
Wir können selbst eine Funktion schreiben (die Methoden des Array-Objekts sind alle im Prototypobjekt definiert), wie folgt:
Array.prototype.unique = function(){
var length = this.length;
if(length <= 1){
return this;
}
if(!Array.prototype.indexOf){
Array.prototype.indexOf = function(item){
var l = this.length, i = 0, r = -1;
if(l <= 0){
return -1;
}
for(; i < l; i++){
if(this[i] === item){
r = i;
}
}
return r;
}
}
var result = []; //去重数组
for(var i = 0; i < length; i++){
if(result.indexOf(this[i]) === -1){
result.push(this[i]);
}
}
return result;
}
Die sechste Methode
Der Array-Typ bietet keine Deduplizierungsmethode. Wenn Sie doppelte Elemente aus dem Array entfernen möchten, müssen Sie selbst einen Weg finden:
function unique(arr) {
var result = [], isRepeated;
for (var i = 0, len = arr.length; i < len; i++) {
isRepeated = false;
for (var j = 0, len = result.length; j < len; j++) {
if (arr[i] == result[j]) {
isRepeated = true;
break;
}
}
if (!isRepeated) {
result.push(arr[i]);
}
}
return result;
}
Die allgemeine Idee besteht darin, die Array-Elemente einzeln in ein anderes Array zu übertragen. Überprüfen Sie während des Übertragungsvorgangs, ob das Element dupliziert ist, und verwerfen Sie es gegebenenfalls direkt. Wie aus verschachtelten Schleifen hervorgeht, ist diese Methode äußerst ineffizient. Wir können eine Hashtabellenstruktur verwenden, um vorhandene Elemente aufzuzeichnen, sodass die innere Schleife vermieden werden kann.
