[JAVA] Rimozione duplicati array

[veilside]

Salve sto cercando di rimuovere gli elementi duplicati all'interno di un'array. l'algoritmo mi elimina gli elementi duplicati fino ad un certo punto dopo riottengo di nuovo i duplicati ad esempio : Se l'array è formato dai seguenti numeri : 0,0,1,1,2,2,3,4,5,6,6,7,7,10 quando mando in run il programma ottengo qeusto output 0,1,2,3,4,5,6,7,10,6,6,7,7,10

int[] a = { 0,0,1,1,2,2,3,4,5,6,6,7,7,10 };
int n = a.length;

int j = 0;
			for(int i = 0 ; i < n ; i++)
			{
				boolean esiste = false;
					for(int k = i+1; k < n; k++)
					{
						if(a[i] == a[k] && esiste == false)
						{
							esiste = true;
						}
					}
					if(esiste == false)
					{
						a[j] = a[i];
						j++;
					}
			}

Se faccio un ciclo per stampare gli elementi distnti del vettore ottengo l'output che ho scritto all'inizio :

//CICLO STAMPA 
for(int w = 0; w<n ; w++)
			{
				System.out.println(a[w]);
			}

se invece inserisco System.out.println(a[i]); all'interno di questo codice ho solo gli elementi distinti :

...
if(esiste == false)
					{
						a[j] = a[i];
						j++;
                                                System.out.println(a[i]);
					}
			}
...

però non è ciò che voglio.. voglio che il ciclo per la stampa mi stampi gli elementi unici..

[Andrea1979]

E' un esercizio scolastico, o un problema "serio"? Nel secondo caso, usa un Set - che si occupa da sè degli elementi duplicati, e quindi travasa tutto in un nuovo vettore.

[Andrea1979]

altrimenti, utilizzando un array d'appoggio, qualcosa del genere:

// se l'array è ordinato. Altrimenti conviene ordinarlo, per mantenere la complessità
//dell'algoritmo lineare.
int[] a = {0,0,1,1,2,2,3,4,5,6,6,7,7,10 };
        int[] b = new int[a.length];

// in ogni caso, il primo elemento di a sarà presente
// nell'array dei non duplicati. Lo aggiungiamo e facciamo i conti
// a partire della posizione successiva
        b[0] = a[0];
// counter tiene conto di quanti elementi diversi ci sono        
        int counter = 1;

// cicliamo su tutti gli elementi di a        
        for (int i = 0; i < a.length; i++) {

// se l'elemento ultimo inserito in b è diverso dall'elemento corrente di a
// allora inseriamo tale elemento in b ed aumentiamo il contantore
            if (b[counter-1] != a[i]) {
                b[counter] = a[i];
                counter++;
            }
        }

// questo serve solo a ripulire l'eventuale output.
        int[] v = new int[counter];
        for (int i = 0; i < v.length; i++) {
            v[i] = b[i];
            System.out.println(v[i]);
        }

[veilside]

grazie della risposta andrea, era quello che cercavo. L'esercizio era in ambito "scolastico" ! Sapevo che in java c'era la set ma non era quello che chiedevo! Ero gia' all'opera per una soluzione simile alla tua ma mi hai anticipato Buona giornata!

[satifal]

Originariamente inviato da Andrea1979
...

// se l'array è ordinato. Altrimenti conviene ordinarlo, per mantenere la complessità
//dell'algoritmo lineare.
...

In effetti se occorre ordinare prima l'array la complessità totale dell'algoritmo non può essere lineare in quanto la complessità degli algoritmi di ordinamento più semplici è O(n^2) mentre il mergesort o il quicksort hanno complessità O(n log n).

[fgiovanni]

se i numeri sono tutti positivi(con qualche controllo in più lo puoi fare anche per i negativi), puoi realizzare l'algoritmo lineare senza fare l'ordinamento, ti spiego,

1)trovi il massimo dell'array(se è già ordinato prendi direttamente l'ultimo).

int max=arr[0]; 
for(int i=1; i<arr.lenght; i++){     
    if(max<arr[i]) max = arr[i]; 
}

2)crei un array booleano di grandezza il valore massimo trovato.
boolean temp[max];

3)fai un ciclo su tutto l'array "arr" e per l'intero che trovi fai:

int new_dim=0;
for(int i=0; i<arr.lenght; i++){
    if(temp[arr[i]] == false){
         dim++;
         temp[arr[i]] = true;
    }
}

adesso sull'array "temp" hai i valori e dim ha la nuova dimensione dell'array che dovrai restituire:

int new_arr[dim];
int cont=0;
for(int i=0; i<temp.lenght; i++){
     if(temp[i]==true){
       new_arr[cont] = i;
       cont++;
     }
}

Spero ti possa essere utile, la comlessità è |-|(N) a discapito dell'utilizzo di memoria però un array booleano non occupa poi così tanto spazio.

[bstefano79]

Originariamente inviato da satifal
In effetti se occorre ordinare prima l'array la complessità totale dell'algoritmo non può essere lineare in quanto la complessità degli algoritmi di ordinamento più semplici è O(n^2) mentre il mergesort o il quicksort hanno complessità O(n log n).

Tanto per passare per quello puntiglioso

quicksort ha complessità media O(n log(n)) ma ha complessità O(n^2) nel caso pessimo
mentre il margesort ha complessità O(n log(n))

[satifal]

Originariamente inviato da bstefano79
Tanto per passare per quello puntiglioso

quicksort ha complessità media O(n log(n)) ma ha complessità O(n^2) nel caso pessimo
mentre il margesort ha complessità O(n log(n))

Hai perfettamente ragione, ma non volevo dilungarmi Tra l'altro se non ricordo male dai miei studi passati il caso pessimo per il quicksort si verifica quando la lista iniziale è ordinata in maniera inversa.

[Pastore12]

Io so eliminare i doppioni senza riordinare!!! Eehhe.

Mi creo una mappa di appoggio (HashMap) e faccio una scansione degli elementi, se un elemento è già nella mappa allora è un doppione, altrimenti lo inserisco nella mappa.

Visto che la mappa è fatta di coppie chiave-valore, la chiave può essere l'elemento, il valore invece il numero di volte in cui compare nella lista originale. Così alla fine della scansione la mappa contiene tutte le informazioni necessarie.

La scansione dei dati e della mappa si fanno ovviamente in tempo lineare, inserimento e ricerca nella mappa richiedono un tempo di ordine logaritmico.
Quindi siamo sempre su n * logn complessivo.

Però siamo fuori dal contesto dell'esercizio, pazienza...

[bstefano79]

Originariamente inviato da satifal
Hai perfettamente ragione, ma non volevo dilungarmi Tra l'altro se non ricordo male dai miei studi passati il caso pessimo per il quicksort si verifica quando la lista iniziale è ordinata in maniera inversa.

dipende dalla politica di scelta del pivot