Supprimer le doublon d'un tableau

Question

Je dois supprimer les entrées en double d'un tableau, mais je ne peux pas utiliser de nouvelles structures de données et le même tableau ne devrait renvoyer que des éléments distincts. Par exemple, si mon tableau est 1,3,3,3,5,55,67,1, le résultat doit être 1,3,5,55,67.

Je crois que j'ai résolu le problème, mais j'ai besoin de votre avis pour savoir si c'est un bon algorithme ou si j'ai besoin de changer quelque chose.

public void DeleteDuplicate(int[] array) 
{ 
    int l = 0; 
    int newPosition = array.Length -1; 
    for (int i = 0; i < array.Length; i++) 
    { 
     for (int j = i + 1; j < array.Length-l; j++) 
     { 
      if (array[i] == array[j]) 
      { 
       int temp = array[j]; 
       array[j] = array[newPosition]; 
       array[newPosition] = temp; 
       newPosition--; 
       l++; 
      } 
     } 
    } 
    Array.Resize(ref array, array.Length - l); 
} 

Answer 1

Votre code est bogué. Essayez de l'exécuter contre {1, 1, 1} - je pense qu'il retournera {1, 1}.

Answer 2

En général, la question de savoir si vous devez maintenir l'ordre relatif des éléments. Par exemple, est-il possible de renvoyer {1, 2} pour l'entrée {2, 1, 2, 1}?

Si elle est autorisée, la solution la plus rapide sera:

• tableau d'entrée de tri
• course une fois à travers elle la comparaison d'un [i] avec [i + 1] et la suppression des doublons dans O (N) '

La complexité totale serait O (N * logN), ce qui est meilleur que N^2 que vous avez proposé.

Si vous devez conserver la commande initiale, je ne suis pas prêt à proposer une solution.

Answer 3

La dernière fois que j'ai coché C# vous a permis de trier 2 tableaux en utilisant un pour les comparaisons et les échanges sur les deux.

Voici ce que vous pouvez faire:

• Créer un tableau indices qui stocke les numéros 0 à N-1.
• Trier array et indices en utilisant array comme clé.
• Recherchez les doublons et définissez les indices des doublons sur N + 1.
• Trier array et indices en utilisant indices comme clé.
• Redimensionnez le tableau à la bonne taille et hop.

Ceci supprime les doublons et préserve la commande.