Comment puis-je supprimer efficacement les doublons d'un tableau sans utiliser d'ensemble ?

Supprimer efficacement les doublons d'un tableau sans recourir à l'ensemble

Vous avez tenté de créer une solution personnalisée pour éliminer les éléments en double d'un tableau, mais des goulots d'étranglement en termes de performances sont apparus. Pour optimiser cette mise en œuvre, nous analyserons les lacunes de votre approche et proposerons des stratégies alternatives.

Analyse de votre algorithme

Votre algorithme tente de rechercher des doublons en comparant chacun élément avec chaque élément suivant. Cette comparaison exhaustive aboutit à une complexité temporelle O(n^2). Pour les grandes baies, cette stratégie peut devenir extrêmement inefficace.

Approche optimisée

Pour améliorer significativement les performances, nous pouvons envisager l'optimisation suivante :

1. Utilisation d'une carte de hachage : Implémentez une carte de hachage pour stocker les éléments uniques rencontrés lors de l'itération. Au fur et à mesure que chaque élément est ajouté au tableau, vérifiez s'il existe déjà en tant que clé dans la carte de hachage. Sinon, ajoutez-le. Cette approche permet des opérations de recherche efficaces à temps constant, réduisant la complexité temporelle à O(n).
2. Tri avant le filtrage : Triez le tableau par ordre croissant. Désormais, les éléments en double seront adjacents les uns aux autres. Parcourez le tableau trié et éliminez les doublons adjacents, ce qui donne un algorithme O(n) en temps linéaire.

Solutions alternatives

Bien que les optimisations susmentionnées puissent améliorer les performances de votre algorithme, vous pouvez également envisager d'autres techniques établies :

• Définir Collections : Comme vous devez éviter d'utiliser Set, nous n'aborderons pas cette option.
• Utilisation d'une collection triée : Semblable au tri avant le filtrage, exploitez une collection triée comme TreeSet ou NavigableSet. Il maintient automatiquement un ordre trié et permet une récupération efficace des éléments, ce qui entraîne une complexité O(n log n).

Mise en œuvre

Basée sur l'approche optimisée, une version modifiée de votre algorithme utilisant une carte de hachage pourrait être :

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

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!