Suppression des doublons dans un tableau en C

La question est un peu complexe. Le problème ici est de supprimer les doublons et d’enregistrer les éléments uniques d’un tableau dans un autre tableau avec leur séquence originale.

Par exemple :

Si l’entrée est entrée bacadt

Le résultat devrait être: bacdt dans l’état exact dans lequel l’entrée a été entrée.

Donc, pour sortinger le tableau, la vérification ne peut pas fonctionner car j’ai perdu la séquence d’origine. On m’a conseillé d’utiliser un tableau d’indices mais je ne sais pas comment faire. Alors, quel est votre conseil pour faire ça?


Pour ceux qui sont disposés à répondre à la question, je voulais append des informations spécifiques.

char** finduni(char *words[100],int limit) { // //Methods here // } 

est la ma fonction. Le tableau dont les doublons doivent être supprimés et stockés dans un tableau différent est constitué de mots [100]. Donc, le processus sera fait à ce sujet. J’ai d’abord envisagé de placer tous les éléments de mots dans un autre tableau et de sortinger ce tableau, mais cela ne fonctionne pas après certains tests. Juste un rappel pour les solveurs :).

Eh bien, voici une version pour les types de caractères. Notez qu’il n’échelle pas.

 #include "stdio.h" #include "ssortingng.h" void removeDuplicates(unsigned char *ssortingng) { unsigned char allCharacters [256] = { 0 }; int lookAt; int writeTo = 0; for(lookAt = 0; lookAt < strlen(string); lookAt++) { if(allCharacters[ string[lookAt] ] == 0) { allCharacters[ string[lookAt] ] = 1; // mark it seen string[writeTo++] = string[lookAt]; // copy it } } string[writeTo] = '\0'; } int main() { char word[] = "abbbcdefbbbghasdddaiouasdf"; removeDuplicates(word); printf("Word is now [%s]\n", word); return 0; } 

Ce qui suit est la sortie:

 Word is now [abcdefghsiou] 

Est-ce quelque chose comme ce que vous voulez? Vous pouvez modifier la méthode s'il y a des espaces entre les lettres, mais si vous utilisez les types int , float , double ou char * , cette méthode ne sera pas mise à l'échelle du tout.

MODIFIER

J'ai posté et puis vu votre clarification, où il est un tableau de caractères char * . Je vais mettre à jour la méthode.


J'espère que ce n'est pas trop de code. J'ai adapté cet algorithme QuickSort et y ai ajouté de la mémoire d'index. L'algorithme est O (n log n), car les 3 étapes ci-dessous sont additives et représentent la complexité la plus défavorable de 2 d'entre elles.

  1. Triez le tableau de chaînes, mais chaque échange doit également être reflété dans le tableau d'index. Après cette étape, le ième élément de originalIndices contient l'index d'origine du ième élément du tableau sortingé.
  2. Supprimez les éléments en double du tableau sortingé en les définissant sur NULL et en définissant la valeur d'index sur elements , qui est la valeur la plus élevée possible.
  3. Triez le tableau d'indices d'origine et assurez-vous que chaque permutation est reflétée dans le tableau de chaînes. Cela nous renvoie le tableau d'origine de chaînes, sauf que les doublons sont à la fin et qu'ils sont tous NULL .
  4. Pour faire bonne mesure, je retourne le nouveau nombre d'éléments.

Code:

 #include "stdio.h" #include "ssortingng.h" #include "stdlib.h" void sortArrayAndSetCriteria(char **arr, int elements, int *originalIndices) { #define MAX_LEVELS 1000 char *piv; int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R; int idx, cidx; for(idx = 0; idx < elements; idx++) originalIndices[idx] = idx; beg[0] = 0; end[0] = elements; while (i>=0) { L = beg[i]; R = end[i] - 1; if (L= 0 && L < R) R--; if (L < R) { arr[L] = arr[R]; originalIndices[L++] = originalIndices[R]; } while (strcmp(arr[L], piv) <= 0 && L < R) L++; if (L < R) { arr[R] = arr[L]; originalIndices[R--] = originalIndices[L]; } } arr[L] = piv; originalIndices[L] = cidx; beg[i + 1] = L + 1; end[i + 1] = end[i]; end[i++] = L; } else { i--; } } } int removeDuplicatesFromBoth(char **arr, int elements, int *originalIndices) { // now remove duplicates int i = 1, newLimit = 1; char *curr = arr[0]; while (i < elements) { if(strcmp(curr, arr[i]) == 0) { arr[i] = NULL; // free this if it was malloc'd originalIndices[i] = elements; // place it at the end } else { curr = arr[i]; newLimit++; } i++; } return newLimit; } void sortArrayBasedOnCriteria(char **arr, int elements, int *originalIndices) { #define MAX_LEVELS 1000 int piv; int beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R; int idx; char *cidx; beg[0] = 0; end[0] = elements; while (i>=0) { L = beg[i]; R = end[i] - 1; if (L= piv && L < R) R--; if (L < R) { arr[L] = arr[R]; originalIndices[L++] = originalIndices[R]; } while (originalIndices[L] <= piv && L < R) L++; if (L < R) { arr[R] = arr[L]; originalIndices[R--] = originalIndices[L]; } } arr[L] = cidx; originalIndices[L] = piv; beg[i + 1] = L + 1; end[i + 1] = end[i]; end[i++] = L; } else { i--; } } } int removeDuplicateStrings(char *words[], int limit) { int *indices = (int *)malloc(limit * sizeof(int)); int newLimit; sortArrayAndSetCriteria(words, limit, indices); newLimit = removeDuplicatesFromBoth(words, limit, indices); sortArrayBasedOnCriteria(words, limit, indices); free(indices); return newLimit; } int main() { char *words[] = { "abc", "def", "bad", "hello", "captain", "def", "abc", "goodbye" }; int newLimit = removeDuplicateStrings(words, 8); int i = 0; for(i = 0; i < newLimit; i++) printf(" Word @ %d = %s\n", i, words[i]); return 0; } 
  1. Parcourez les éléments du tableau – Opération O(n)
  2. Pour chaque élément, ajoutez-le à un autre tableau sortingé
  3. Avant de l’append au tableau sortingé, vérifiez si l’entrée existe déjà – Opération O(log n)

Enfin, opération O(n log n)

Je pense qu’en C, vous pouvez créer un second tableau. vous ne copiez ensuite l’élément du tableau d’origine que si cet élément ne figure pas déjà dans le tableau d’envoi. Cela préserve également l’ordre de l’élément.

Si vous lisez l’élément un à un, vous pouvez le supprimer avant de l’insérer dans le tableau d’origine, ce qui pourrait accélérer le processus.

Comme Thomas l’a suggéré dans un commentaire, si chaque élément du tableau est garanti à partir d’un ensemble limité de valeurs (tel qu’un caractère), vous pouvez y parvenir en un temps O(n) .

  1. Conservez un tableau de 256 bool (ou int si votre compilateur ne prend pas en charge bool ) ou le nombre de valeurs discrètes possibles dans le tableau. Initialise toutes les valeurs sur false .
  2. Analysez le tableau d’entrée un par un.
  3. Pour chaque élément, si la valeur correspondante dans le tableau bool est false , ajoutez-la au tableau de sortie et définissez la valeur de ce dernier sur true . Sinon, ne faites rien.

Vous savez comment le faire pour le type char, non? Vous pouvez faire la même chose avec des chaînes, mais au lieu d’utiliser un tableau de bools (qui est techniquement une implémentation d’object “set”), vous devez simuler le “set” (ou tableau de bools) avec un tableau linéaire de chaînes. vous avez déjà rencontré. C’est-à-dire que vous avez déjà vu un tableau de chaînes. Pour chaque nouvelle chaîne que vous vérifiez si elle se trouve dans un tableau de chaînes “seen”, si c’est le cas, alors vous l’ignorez (non unique), si ce n’est pas dans un tableau à la fois tableau de chaînes vues et sortie. Si vous avez un petit nombre de chaînes différentes (moins de 1 000), vous pouvez ignorer les optimisations de performances et comparer simplement chaque nouvelle chaîne avec tout ce que vous avez déjà vu auparavant.

Cependant, avec un grand nombre de chaînes (quelques milliers), vous devrez optimiser un peu les choses:

1) Chaque fois que vous ajoutez une nouvelle chaîne à un tableau de chaînes que vous avez déjà vu, sortingez le tableau avec l’algorithme de sorting par insertion. N’utilisez pas quickSort, car le sorting par insertion a tendance à être plus rapide lorsque les données sont presque sortingées.

2) Lorsque vous vérifiez si la chaîne est dans le tableau, utilisez la recherche binary.

Si le nombre de chaînes différentes est raisonnable (c’est-à-dire que vous n’avez pas des milliards de chaînes uniques), cette approche devrait être assez rapide.