Comment puis-je détecter efficacement les entiers en double dans un tableau Java ?

Reconnaître les doublons dans un tableau Java : un voyage

Dans le domaine de Java, une tâche intégrale souvent rencontrée consiste à rechercher des éléments en double dans un tableau d'entiers (int []). Cependant, un piège courant survient lorsque l’on tente d’identifier ces doublons. Explorons le problème et ses solutions.

Considérez le code suivant :

int[] zipcodelist = // ...

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

Ce code vise à déterminer si la liste de codes postaux donnée contient des éléments en double. Cependant, il ne tient pas compte des scénarios dans lesquels aucun doublon n’existe. En conséquence, les doublons finissent toujours par être vrais.

Identifier le défaut

Pour comprendre le défaut, analysons la logique. Le code comporte des boucles imbriquées qui comparent chaque élément de la liste avec tous les autres éléments. Si deux éléments correspondent, les doublons sont définis sur true, indiquant la présence de doublons. Cependant, lorsqu’il n’y a pas de doublons, la boucle compare inévitablement un élément avec lui-même. Pour chaque élément, cette auto-comparaison définirait les doublons sur vrai.

Une approche corrigée

Pour garantir une détection correcte des doublons, le code doit exclure les auto-comparaisons. Une façon d'y parvenir consiste à modifier la structure de la boucle imbriquée comme suit :

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j &amp;&amp; zipcodeList[k] == zipcodeList[j])
      duplicates=true;

Cette modification ignore les auto-comparaisons en démarrant la boucle interne à l'index suivant (k=j 1).

Explorer des solutions alternatives

Bien que l'approche corrigée fonctionne efficacement, il existe des alternatives plus rapides. Considérez la solution suivante basée sur un hashmap :

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

Cette solution utilise un jeu de hachage pour vérifier efficacement les éléments en double. Chaque élément est ajouté au jeu de hachage, et si un élément est déjà présent, cela signifie un doublon.

Une autre approche efficace consiste à utiliser un bitmap :

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodelist)
     if (!(bitmap[item] ^= true)) return true;
   }
   return false;
}

Cette solution crée un bitmap tableau de taille égale à la valeur maximale possible dans le tableau (MAXZIP). Il utilise ensuite la manipulation des bits pour définir le bit correspondant à chaque élément rencontré dans le tableau d'entrée. Si un bit est déjà défini, cela indique un doublon.

Résultats de l'analyse comparative

Pour évaluer les performances de ces approches, nous avons effectué une analyse comparative avec différentes tailles de liste. Les résultats ont montré que l'approche bitmap s'est révélée clairement gagnante en termes d'efficacité, en particulier pour les listes plus grandes :

Array Size	Bitmap (ms)	Hash Set (ms)	Nested Loops (ms)
10	0.0	0.0	0.0
1,000	0.0	0.0	0.0
10,000	0.0	0.0	100.0
100,000	0.0	0.16	9,923.3

Conclusion

Identifier les doublons dans un tableau Java peut être une tâche simple une fois les pièges compris. En évitant les auto-comparaisons ou en tirant parti d'approches alternatives telles que les jeux de hachage et les bitmaps, une détection efficace et précise des doublons peut être obtenue, optimisant ainsi les performances de vos applications Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!