Altro problema tipico. Verificare se in un vettore sono presenti due elementi uguali.
Prima soluzione.
Prendo il primo elemento e scorro il resto del vettore per vedere se questo è presente, poi prendo il secondo elemento e verifico se è presente nei restanti n-2 elementi e così di seguito.
Nel caso pessimo abbiamo n-1 + n-2 + ..... 2+1 operazioni.
Ricordando che 1+2+...+n è uguale a n*(n+1)/2 l'algoritmo ha complessità O(n2)
Seconda soluzione
Si ordina preventivamente il vettore e poi si verifica se due elementi consecutivi sono uguali.
Quindi, sapendo che il costo dell'ordinamento è O(n*log n) e lo scorrimento è O(n), otteniamo un costo totale di O(n*log n).
Terza soluzione
Questa soluzione è applicabile nel caso in cui i valori del vettore siano numeri interi.
Si crea un vettore di appoggio W lungo quanto il massimo elemento presente nel vettore V da controllare. Si scorre V e per ogni elemento si va ad incrementare il valore contenuto nella cella di W indicizzata dall'elemento V[i].
Se in qualsiasi momento si ha che il contenuto di una cella di W diventa 2 allora questo indica che l'elemento corrispondete all'indice è presente due volte in V.
Complessità O(n).
Condividi e segnala 
