Quatre méthodes pratiques pour supprimer les doublons des compétences js arrays_javascript

Une question à laquelle les enquêteurs front-end doivent se préparer : Comment supprimer les doublons du tableau Javascript. Pour autant que je sache, Baidu, Tencent, Shanda, etc. ont tous posé cette question lors d'entretiens. Cette question semble simple, mais elle recèle en réalité des dangers cachés. Le test ne porte pas seulement sur la mise en œuvre de cette fonction, mais également sur votre compréhension approfondie de l'exécution d'un programme informatique.

J'ai proposé un total de trois algorithmes pour y parvenir :

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;
}

Les première et troisième méthodes utilisent toutes deux la méthode indexOf du tableau. Le but de cette méthode est de trouver la première occurrence du paramètre stocké dans le tableau. Évidemment, le moteur js parcourra le tableau jusqu'à ce qu'il trouve la cible lors de l'implémentation de cette méthode. Cette fonction fait donc perdre beaucoup de temps. La deuxième méthode utilise une table de hachage. Stockez les occurrences dans un objet sous forme d'indices. Les références en indice sont beaucoup plus rapides que la recherche dans le tableau à l'aide de indexOf.

Afin de juger de l'efficacité de ces trois méthodes, j'ai réalisé un programme de test pour générer un tableau de nombres aléatoires d'une longueur de 10 000, puis j'ai utilisé plusieurs méthodes pour tester le temps d'exécution. Les résultats montrent que la deuxième méthode est beaucoup plus rapide que les deux autres méthodes. Cependant, en termes d'utilisation de la mémoire, la deuxième méthode est plus susceptible d'être utilisée car il existe une table de hachage supplémentaire. C'est ce qu'on appelle l'espace-temps. Ceci est la page de test, vous pouvez également la consulter.

J'ai écrit une quatrième méthode :

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;
}

L'idée de cette méthode est de trier d'abord le tableau, puis de comparer deux valeurs adjacentes. La méthode de tri native JS est utilisée lors du tri. Le moteur JS doit utiliser le tri rapide en interne. Le résultat final du test est que le temps d'exécution de cette méthode est en moyenne environ trois fois supérieur à celui de la deuxième méthode, mais il est beaucoup plus rapide que les première et troisième méthodes.