Angella Andrea - Italian Blog

Infinita passione per lo sviluppo software !
posts - 133, comments - 216, trackbacks - 9

My Links

News

MIT OpenCourseWare: I'm invested Wikipedia Affiliate Button


Sto leggendo:

Archives

Post Categories

Siti web realizzati

Siti web tecnici

Algoritmi – Rimuovere i duplicati da un lista


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

2010-09-06_234517

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;
        }
    }
}

Print | posted on Tuesday, September 7, 2010 12:50 AM | Filed Under [ Algoritmica ]

Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET