Comment pouvons-nous optimiser un algorithme de suppression des doublons pour les grands tableaux sans utiliser les fonctions d'ensemble intégrées ?

Optimisation de l'algorithme de suppression des doublons d'un tableau

Le code fourni vise à supprimer les valeurs en double d'un tableau sans utiliser d'outils intégrés tels que Set ou itérateurs. Cependant, il se heurte à des goulots d’étranglement en termes de performances lorsqu’il traite un grand nombre d’éléments. Ce problème provient de la structure de boucle imbriquée, où chaque élément est comparé à tous les éléments suivants.

Pour améliorer l'efficacité de l'algorithme, envisagez la stratégie d'optimisation suivante :

Utiliser un HashSet :

Bien que la tâche interdise explicitement l'utilisation de Set ou HashSet, il convient de noter qu'un HashSet fournit une solution efficace pour éliminer des doublons. Sa mise en œuvre utilise une table de hachage pour suivre l'existence de chaque élément, permettant une recherche et une insertion en temps constant.

Set<Integer> uniqueValues = new HashSet<>();

for (int num : arr) {
    uniqueValues.add(num);
}

L'ensemble de valeurs uniques résultant ne contiendra que des éléments distincts.

Préserver l'ordre des éléments :

Si la préservation de l'ordre d'origine des éléments est cruciale, une version modifiée de l'algorithme fourni peut être employé :

// Create a boolean array to track duplicates
boolean[] duplicates = new boolean[arr.length];

// Find and mark duplicates in the first iteration
for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] == arr[j]) {
            duplicates[j] = true;
        }
    }
}

// Create a new array to store unique values
int[] uniqueArr = new int[arr.length - duplicates.length];
int uniqueIndex = 0;

// Copy unique values into the new array
for (int i = 0; i < arr.length; i++) {
    if (!duplicates[i]) {
        uniqueArr[uniqueIndex++] = arr[i];
    }
}

return uniqueArr;

Cet algorithme atteint une complexité temporelle O(n²) tout en préservant l'ordre des éléments d'origine.

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!