Comment puis-je rechercher efficacement des entiers en double dans un tableau Java ?

Recherche de doublons dans un tableau Java

Le problème

Vous disposez d'un tableau d'entiers et souhaitez identifier efficacement les doublons. Votre code initial, tentant de comparer chaque paire d'éléments, ne parvient pas à détecter avec précision les doublons lorsqu'il n'en existe pas.

Le problème

Le défaut du code réside dans sa dépendance à l'égard de l'indicateur de doublons en cours d'initialisation. à faux dans tous les cas. Si aucun doublon n'est trouvé, la boucle définira toujours les doublons sur vrai lors de la vérification des éléments diagonaux (c'est-à-dire lorsque j == k).

Une solution plus nuancée

Pour remédier à cela, assurez-vous que l'indicateur de doublons est défini sur true uniquement lorsque des doublons réels sont trouvés. Ceci peut être réalisé en omettant les comparaisons de zipcodeList[j] avec lui-même lorsque j == k.

Voici le code révisé :

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

Une approche plus rapide

Le La solution ci-dessus a une complexité d'exécution de O(n²), où n est le nombre d'éléments dans le tableau. Pour les grands tableaux, cette approche peut s'avérer inefficace.

Une méthode plus efficace pour détecter les doublons consiste à tirer parti d'une approche basée sur le hachage, réduisant ainsi la complexité temporelle à O(n). Voici un exemple utilisant un HashSet :

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

Alternativement, une solution O(n) peut être obtenue en utilisant un tableau boolean[] (bitmap) pour suivre les éléments rencontrés précédemment et définir les doublons sur true lorsqu'un élément est rencontré une seconde fois.

Conclusion

En fonction de la taille du tableau d'entrée et de la fréquence des doublons, le choix de l'approche doit être adapté pour optimiser l’efficacité.

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!