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 soluzioneSi 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 soluzioneQuesta 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).
Elementi ripetuti in un vettore
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 soluzioneSi 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 soluzioneQuesta 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).