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.
originalIndices
contient l'index d'origine du ième élément du tableau sortingé. NULL
et en définissant la valeur d'index sur elements
, qui est la valeur la plus élevée possible. NULL
. 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; }
O(n)
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)
.
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
. 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.