Supprimez les doublons du tableau et enregistrez-le dans un autre

Nov 23 2020

J'ai donc été chargé de créer un tableau sans valeurs dupliquées à partir d'un autre tableau existant. Alors je l'ai fait, mais je veux savoir s'il existe une autre meilleure façon de le faire.

Exemple d'entrée / sortie:

Input: 10, 15, 10, 5, 1, 3

Output: 10, 15, 5, 1, 3

Voici donc mon code.

#include <stdio.h>

int main(void) {
  const int MAX_ARRAY_SIZE = 5;

  int m[MAX_ARRAY_SIZE], p[MAX_ARRAY_SIZE];


  for(int i = 0; i < MAX_ARRAY_SIZE; i++) {
    printf("Enter number: ");
    scanf("%d",&m[i]);
  }
  int k = 0;
  int dup = 0;
  for(int i =0; i < MAX_ARRAY_SIZE; i++) {
    for(int j = i +1; j <MAX_ARRAY_SIZE; j++) {
        if(m[i] == m[j]) {
            dup = 1;
        }
    }
    if(dup != 1) {
      p[k++] = m[i];
    }
    dup = 0;
  }

  printf("The new array without repeated values\n");
  for(int i = 0; i < k; i++) {
    printf("%d\n",p[i]);
  }

  return 0;
}

Je ne suis pas sûr que ce soit la manière juste et simple de le faire. Je veux quelques suggestions.

Merci d'avance. :)

Réponses

4 Reinderien Nov 23 2020 at 22:31

Résiliation anticipée

Après

        dup = 1;

tu devrais break. Il n'est pas nécessaire d'exécuter le reste de la boucle.

Booléens

Envisagez de l'utiliser <stdbool.h>, de le créer bool dup = false, de l'attribuer plus tard trueet d'écrire if (!dup).

Complexité

En termes pratiques, un tableau de cinq valeurs ne pose aucun coût de calcul. Cependant, si votre professionnel se soucie de l'analyse de la complexité, la solution «appropriée» à cela devrait se terminer en temps linéaire (plutôt que votre temps quadratique actuel), en utilisant quelque chose comme un ensemble de hachage, avec un pseudocode:

Set *seen = make_set();
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
    int m;
    scanf(&m);
    if (!contains(seen, m))
        add(seen, m);
}

for (m in seen)
    printf(m);
Noname Nov 24 2020 at 16:07

Ce Q a besoin d'un certain déduplication lui-même. Supprimez les doublons ... Mais comme c'est ma troisième version de la boucle interne, je profite d'un nouveau départ.

Cette affectation inoffensive int j = i + 1;, à l'origine emballée dans la for-expression-list, fait plus que simplement initialiser jpour le dernier i: elle rend m[j]illégale / indéfinie.

Le but (?) Est d'éviter le dupdrapeau et de "normaliser" les boucles. Je pense que ce réarrangement en vaut la peine:

    int j;
    for (int i = 0; i < ARRAY_SIZE; i++) {
        j = i;
        do
            if (++j == ARRAY_SIZE) {   // already past end?    
                p[k++] = m[i];            // copy this one
                break;                    // and finish
            }
        while (m[i] != m[j]);          // if match, then just finish 
    }

Maintenant, tout est à la place naturelle.

J'ai écrit do statement while (expr);sans accolades pour illustrer la structure. Ce qui est un peu caché, c'est l'incrément de boucle if (++j....


Au lieu d'une structure réelle (triée), on peut utiliser le nouveau tableau unique pour rechercher des doublons. En raison du 0déjà dans le nouveau tableau, je copie d'abord le premier élément sans condition, puis je démarre la boucle avec le deuxième élément.

    int k = 1;
    /* First is always unique */
    printf("m[0] -> p[0]\n");
    p[0] = m[0];
    for (int i = 1; i < ARRAY_SIZE; i++)
        for (int j = 0;; j++) {
            if (j == k) {         
                printf("m[i=%d] -> p[k=%d]\n", i, k);
                p[k++] = m[i];
                break;
            }
            if (p[j] == m[i])
                break;
        }

Cela if (p[j] == m[i])doit quand même être logiquement après if (j == k), donc la boucle for doit être un peu freestylée.

Les printfs illustrent:

Enter number: 6
Enter number: 6
Enter number: 0
Enter number: 0
Enter number: 8
m[0] -> p[0]
m[i=2] -> p[k=1]
m[i=4] -> p[k=2]
The array without repeated values
6
0
8

Effet secondaire: l'ordre est désormais conservé.

Je suppose que c'est un peu délicat car la recherche et l'insertion sont si étroitement liées. L' kindex doit être manipulé avec précision. (les autres aussi)

Performances: je ne sais même pas si l'utilisation du nouveau tableau jusqu'à k est plus rapide que la recherche OP dans le reste de l'original. Cela semble être le même, du moins dans certains cas.

Le problème est que le nouveau tableau n'est pas trié. Le garder trié coûte trop cher s'il est fait naïvement, après chaque insertion.

Il faudrait donc «étaler» d'abord pour effectuer une recherche efficace. Pour les entiers (aléatoires), modulo 10 peut créer dix tableaux différents - ou buckets. Avec un 2D b[][](au lieu de OP p[])

b[0] {100}
b[1] {1, 31, 20001}
b[2] {12, 32, 502}
b[3] {}
b[4] {94}
...

Chaque (sous) tableau a besoin de l'original ARRAY_SIZEdans le pire des cas. Mais maintenant, le tableau pour rechercher des dups est 10 fois plus court en moyenne.


Ainsi, vous pouvez changer l'entrée interactive en un générateur de tableau d'un million d'entiers et faire quelques tests.


Tout cela à cause de cet dupindicateur de boucle;)