Rimozione di duplicati da un elenco confrontandolo con un altro elenco

Question

Ho due elenchi di oggetti e vorrei rimuovere le istanze da un elenco che è presente in un altro elenco.

ad es. Ho seguito due liste e suppongo che ogni lettera rappresenti l'oggetto.

Elenco elencoA = {A, B, C, D, E, F, G, H, I, J}

Elenco elencoB = {D, G, K, P, Z}

ora, chiaramente elencoB ha D e G, che ci sono su elencoA troppo quindi voglio elencoA essere come questo

elencoA = {a, B, C, e, F, H, I, J}

Can voi per favore suggerite quale sarebbe la soluzione per questo con O (n) o meno di O (n2).

Posso scorrere tutte e due le liste e rimuovere le istanze duplicate confrontandole ma voglio avere qualcosa di più efficiente.

Answer 1

si potrebbe aggiungere entrambi gli elementi della lista a un Set

Per rimuovere gli elementi in una sola lista da un altro, provare listA.removeAll(listB);

Answer 2

Come risposto ssantos, è possibile utilizzare un set.

In alternativa, se gli elenchi sono ordinati, è possibile alternativamente scorrere tra di loro. Scorrere l'elenco fino a raggiungere un elemento maggiore dell'elemento corrente di ListB, quindi scorrere su ListB finché non si raggiunge un elemento maggiore dell'elemento corrente di ListA, ecc.

Answer 3

Se gli elenchi non sono ordinati, e sono ArrayList o altre implementazioni di elenchi simili con un metodo O (n) contiene, quindi è necessario creare un HashSet con gli elementi di listB per eseguire la rimozione. Se gli elementi non sono messi in un set, si finirà con prestazioni O (n^2).

modo più semplice per fare quello che ti serve è quindi:

listA.removeAll(new HashSet(listB)); 

ArrayList.removeAll(Collection) non mettere gli elementi in un set per voi (almeno nel JDK 1.6 e 1.7 versioni ho controllato), motivo per cui si è necessario creare il HashSet da soli in precedenza.

Il metodo removeAll copierà gli elementi che si desidera conservare in cima alla lista come si attraversa esso, evitando gamma compattazione con ogni rimozione, in modo da utilizzare contro un passato in HashSet come mostrato è ragionevolmente ottimale ed è O (n).

Answer 4

Di seguito è riportato qualche pseudo-C da risolvere nel tempo previsto O(n).

lenA = length pf listA 
lenB = length of listB 
shortList = (lenA <= lenB) ? A : B 
longList = (shortList == A) ? B : A 

create hash table hashTab with elements of shortList 

for each element e in longList: 
    is e present in hashTab: 
     remove e from longList 

now, longList contains the merged duplicate-free elements