Gymnastique algorithmique 11

Remove Duplicates from a Linked List Scannez à partir de la tête de la LinkedList, supprimez les nœuds en double et renvoyez la tête de la LinkedList sans doublons.

La description

Compte tenu de la LinkedList suivante: Si vous supprimez 28 et 14 qui ont des données en double, vous obtiendrez la liste liée suivante. Solution Runtime Complexity O(n) Le temps d'exécution est O (n) car il analyse la LinkedList non triée pour les doublons. Space Complexity O(n) La structure de données de HashSet est utilisée pour distinguer s'il est dupliqué, et s'il n'y a pas de données dupliquées, le pire est O (n).

la mise en oeuvre

removeDuplicate.java

class removeDuplicate{
  public LinkedListNode remove_duplicates(LinkedListNode head) 
  {
    if (head == null || head.next == null) {
      return head;
    }

    LinkedListNode cur = head;
    LinkedListNode prev = head;

    HashSet set = new HashSet();

    while (cur != null) {
      if (!set.contains(cur.data)) {
        set.add(cur.data);
        prev = cur;
      } else {
        prev.next = cur.next;
      }
      cur = cur.next;
    }
    return head;
  }
}

Pensées

L'algorithme est simple, utilisant deux pointeurs pour remplir le HashSet. Si le pointeur et le cur rencontrent des données en double, utilisez le pointeur et précisez ce point vers le nœud immédiatement avant le cur. Prev.next = cur.next ignore les nœuds avec des données en double. S'il y a assez de mémoire, je pense qu'il n'y a pas de problème avec une telle implémentation.

Cependant, si votre mémoire est limitée, vous devez sacrifier le temps d'exécution. Si vous êtes autorisé à réorganiser la LinkedList, vous pouvez trier par heure O (n logn). Après le tri, les nœuds contenant toutes les données dupliquées sont adjacents et peuvent être supprimés avec un balayage linéaire.

Si la réorganisation n'est pas autorisée Pour chaque nœud de la LinkedList, vous rechercherez les nœuds du nœud précédent contenant les mêmes données. Cet algorithme est O (n ^ 2) et ne nécessite pas d'espace supplémentaire, mais au détriment d'un temps d'exécution important.