individuazione dell'elemento non comune tra due array

Question

In un'intervista è stato chiesto di trovare elementi non comuni tra due array di stringhe.

Eg: String a[]={"a","b","c","d"}; 
String b[]={"b","c"}; 
O/p should be a,d 

Ho risposto alla domanda che in Java Set è implementato utilizzando HashTable. Il codice con l'insieme è molto più semplice:

String[] a = {"a","b","c","d"}; 
String[] b = {"b", "c"}; 

Set<String> set = new HashSet<>(a.length); 
for(String s : a){ 
    set.add(s); 
} 
for(String s : b){ 
    set.remove(s); 
} 
return set; 

ora la mia domanda è che c'è qualche altro approccio migliore per raggiungere questo obiettivo

Answer 1

Prova questa:

String a[]={"a","b","c","d"}; 
String b[]={"b","c"}; 

List aLst = new ArrayList(Arrays.asList(a)); 
List bLst = new ArrayList(Arrays.asList(b)); 

aLst.removeAll(bLst); 
System.out.println(aLst); 

Answer 2

Se [x,y], [x,z] dovrebbe produrre [y,z] Ecco cosa Suggerisco:

String[] a = {"a","b","c","d"}; 
String[] b = {"b", "c", "x"}; 

Set<String> set = new HashSet<>(Arrays.asList(a)); 
for (String s : new HashSet<>(Arrays.asList(b)) { 
    if (!set.add(s)) // if it's already present 
     set.remove(s); // remove it from the result 
} 

Se d'altra parte, [x,y], [x,z] dovrebbe produrre [y], vorrei suggerire

Set<String> set = new HashSet<>(Arrays.asList(a)); 
set.removeAll(Arrays.asList(b)); 

Answer 3

è possibile abbreviare il codice da

TreeSet set = new TreeSet(Arrays.asList(a)); 
set.removeAll(Arrays.asList(b)); 

Demo

Answer 4

avrei gestire questo in tre fasi:

• Trova tutti gli elementi in a ma non b
• Trova tutti gli elementi in b ma non a
• aggiungere questi due set insieme

Così, per esempio:

Set<String> aSet = new HashSet<>(Arrays.asList(a)); 
Set<String> bSet = new HashSet<>(Arrays.asList(b)); 

Set<String> aNotB = new HashSet<>(aSet); 
aNotB.removeAll(bSet); 

Set<String> bNotA = new HashSet<>(bSet); 
bNotA.removeAll(aSet); 

Set<String> onlyOne = new HashSet<>(aNotB); 
onlyOne.addAll(bNotA); 

(Il codice di flusso in Java 8 potrebbe rendere questo più semplice anche. ..)

Il codice potrebbe essere abbreviato se non si preoccupa di modificare aSet e bSet, ma io trova questa versione più facile da leggere.

Answer 5

In effetti, questo amplia la risposta di Jon Skeet, ma lo fa utilizzando i flussi di Java 8.

String[] result = Arrays.stream(a) 
         .filter((s) -> Arrays.stream(b).noneMatch(s::equals)) 
         .toArray(String[]::new); 

System.out.println(Arrays.toString(result)); 

I principali inquilini del codice sono:

• filtrare qualsiasi elemento contenuto in A se e solo se non esiste in B (tramite l'operatore terminale cortocircuito noneMatch), controllando se l'elemento è uguale a qualcosa in quel flusso.
• Raccogliere i risultati in un String[].

Un altro approccio con Set, e ancora una volta utilizzando i flussi:

Set<String> setA = new HashSet<>(Arrays.asList(a)); 
Set<String> setB = new HashSet<>(Arrays.asList(b)); 

String[] setResult = setA.stream() 
         .filter((s) -> !setB.contains(s)) 
         .toArray(String[]::new); 

Il problema principale con il codice non-Set come sottolineato è che è giunto il momento quadratica nel caso peggiore. Questo codice sfrutta il tempo di accesso costante a Set#contains e dovrebbe essere eseguito in un tempo lineare.

Answer 6

Se le stringhe sono solo lettere inglesi (o su un piccolo alfabeto .. anche ASCII), preferisco usare un valore booleano [] per valore char invece di HashSet ecc per migliorare leggermente le prestazioni.