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

Suppression efficace des duplications de tableaux sans ensembles

Dans certains défis de programmation, vous devrez peut-être supprimer les valeurs dupliquées d'un tableau sans utiliser des éléments prédéfinis des structures de données comme Set ou HashSet. Voici une approche optimisée que vous pouvez envisager :

L'implémentation que vous fournissez effectue plusieurs passes sur le tableau, ce qui entraîne une complexité temporelle inefficace. Pour l'améliorer, pensez à utiliser une combinaison de deux optimisations :

1. Utilisez un tableau de marqueurs :

Créez un tableau de marqueurs de taille égale à l'élément maximum dans le tableau d'origine. Initialisez tous les éléments à 0. Lorsque vous rencontrez un élément dans le tableau d'origine, définissez la position correspondante dans le tableau de marqueurs sur 1. De cette façon, il vous suffit de vérifier le tableau de marqueurs pour déterminer si un élément est un doublon ou non.

2. Utiliser le pointeur d'index de fin :

Maintenir un pointeur d'index de fin qui indique l'index jusqu'à lequel le tableau sans doublons a été calculé. Lorsque vous rencontrez un doublon, déplacez les éléments après le doublon vers la gauche, en décrémentant l'index de fin en conséquence.

Voici une version optimisée de votre code utilisant ces optimisations :

public static int[] removeDuplicates(int[] arr) {
    // Initialize the marker array with zeros
    int[] marker = new int[1000000];
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        // Check if the element is already marked as duplicate
        if (marker[arr[i]] == 1) {
            // If it's a duplicate, shift the elements after it to the left
            for (int j = i + 1; j < end; j++, i++) {
                arr[i] = arr[j];
            }
            end--;
            i--;
        } else {
            // If it's not a duplicate, mark it in the marker array
            marker[arr[i]] = 1;
        }
    }

    return arr;
}

Cette implémentation améliore considérablement les performances en évitant plusieurs passages sur le tableau et en réduisant le nombre d'échanges d'éléments requis.

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!