Problema:
Considerare una semplice classe che implementa una SingleLinkedList non ordinata di interi. Realizzare un metodo per rimuovere tutti i duplicati dalla lista.
Input:
Niente
Output:
Niente.
Internamente gli elementi duplicati saranno rimossi dalla lista.
Esempio:
Lista iniziale:
1, 1, 1, 1, 3, 4, 5, 3, 5, 1, 2, 1, 2, 3, 4 ,1 , 2, 3, 5, 1, 2, 5, 6, 7, 2, 8, 2, 9, 9
Lista finale:
1, 3, 4, 5, 2, 6, 7, 8, 9
La struttura dati
Il mio ragionamento:
Prendo il valore dell’elemento di testa. Scorro tutti gli elementi successivi. Se uno degli elementi successivi e’ duplicato aggiorno i puntatori in modo da bypassarlo. Ripeto il procedimento per l’elemento successivo della lista e cosi’ via.
La complessita’ di questo algoritmo e’ O(N^2).
La mia soluzione:
public void RemoveDuplicates()
{
if (head == null) return;
Node p = head;
while (p != null)
{
int value = p.Value;
Node q = p;
while (q.Next != null)
if (q.Next.Value == value) q.Next = q.Next.Next;
else q = q.Next;
p = p.Next;
}
}
Una soluzione piu’ efficiente
Se si utilizza un dizionario e’ possibile portare la complessita’ dell’algoritmo a poco piu’ di O(N)
public void RemoveDuplicates_Using_Dictionary()
{
if (head == null) return;
var d = new Dictionary<int, bool>();
d[head.Value] = true;
Node node = head;
while (node.Next != null)
{
int value = node.Next.Value;
if (d.ContainsKey(value))
{
node.Next = node.Next.Next;
}
else
{
d[value] = true;
node = node.Next;
}
}
}