[JAVA] 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: Screen Shot 2020-01-04 at 12.00.09.png Si vous supprimez 28 et 14 qui ont des données en double, vous obtiendrez la liste liée suivante. Screen Shot 2020-01-04 at 12.00.23.png 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.

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes