Trova il valore duplicato dall'array di stringhe

Question

Ho trovato due modi per trovare il valore duplicato dall'array di stringhe.

Primo modo:

private static String FindDupValue(String[] sValueTemp) { 
    for (int i = 0; i < sValueTemp.length; i++) { 
     String sValueToCheck = sValueTemp[i]; 
     if(sValueToCheck==null || sValueToCheck.equals(""))continue; 
     for (int j = 0; j < sValueTemp.length; j++) { 
     if(i==j)continue; 
     String sValueToCompare = sValueTemp[j]; 
     if (sValueToCheck.equals(sValueToCompare)){ 
      return sValueToCompare; 
     } 
     } 

    } 
    return ""; 

    } 

Secondo modo:

private static String FindDupValueUsingSet(String[] sValueTemp) { 
    Set<String> sValueSet = new HashSet<String>(); 
    for(String tempValueSet : sValueTemp) { 
     if (sValueSet.contains(tempValueSet)) 
     return tempValueSet; 
     else 
     if(!tempValueSet.equals("")) 
      sValueSet.add(tempValueSet); 
    } 
    return ""; 
    } 

Entrambi i metodi sono corretti.

La mia domanda è quale metodo migliore e perché? O c'è qualche altro modo migliore per scoprire il valore duplicato di un array?

Answer 1

Secondo modo.

L'utilizzo di un set è molto più efficiente per questa operazione perché sValueSet.contains(tempValueSet) utilizza la mappa di supporto (e quindi codici hash e tempi di ricerca rapidi) anziché iterare completamente.

Answer 2

Entrambi gli approcci sono quasi simili in termini di complessità algoritmica.

La complessità del primo approccio è O(N * N), dove N è la lunghezza dell'array. Non penso sia necessario spiegare il perché, ma nel caso lo sia: i cicli nidificati prendono le unità di tempo N * N, il che dà la complessità.

Per quanto riguarda il secondo approccio, disporre di HashSet consente di eseguire ricerche con la complessità costante (O(1)), poiché la ricerca è basata sul valore hash dello String. Si può pensare che questo approccio sia più efficace, ma in realtà non è così tanto, perché abbiamo bisogno di trovare l'operazione insert su HashSet.

L'aggiunta allo HashSet è di complessità O(N) (scenario peggiore). Per gli oggetti stringa N, è possibile che le operazioni di inserimento di N inseriscano nuovamente la complessità di O(N * N).

Quindi, per riassumere, entrambi gli approcci sono di spesa simile. Preferirei il secondo, anche se è un po 'più leggibile.

Answer 3

La cosa bella di Set è che è add operation restituisce true se questo set non contiene già l'elemento specificato.

public static void main(String[] args) { 
    Set<String> set = new HashSet<>(); 
    String[] stringsToTest = {"a", "b", "c", "a"}; 

    for (String s : stringsToTest) { 
     boolean notInSetYet = set.add(s); 

     if (!notInSetYet) { 
      System.out.println("Duplicate: " + s); 
     } 
    } 
} 

uscita:

duplicato: un

Answer 4

nel vostro primo approccio nel secondo ciclo Credo che se si modifica il punto di loop di partenza da j = 0 per j = i it lo renderà più veloce. perché si evita di confrontare 2 valori due volte

private static String FindDupValue(String[] sValueTemp) { 
for (int i = 0; i < sValueTemp.length; i++) { 
    String sValueToCheck = sValueTemp[i]; 
    if(sValueToCheck==null || sValueToCheck.equals(""))continue; 
    for (int j = i; j < sValueTemp.length; j++) { 
    if(i==j)continue; 
    String sValueToCompare = sValueTemp[j]; 
    if (sValueToCheck.equals(sValueToCompare)){ 
     return sValueToCompare; 
    } 
    } 

} 
return ""; 

}

Answer 5

Questo sembra essere uno degli approcci più veloci, in esecuzione in O (n), assumendo un O ammortizzato (1) per HashSet.add, più che richiede solo un calcolo hash per iterazione omettendo l'uso di contains. È vero che String hashcode nella cache (grazie a Jonah), questo codice generalizza il concetto di omissione dello contains.

private static String FindDupValueUsingSet(String[] sValueTemp) { 
    Set<String> sValueSet = new HashSet<String>(); 
    for(String tempValueSet : sValueTemp) 
     if (!tempValueSet.equals("")) //exclude empty Strings (add null checking if required) 
      if (!sValueSet.add(tempValueSet)) 
       return tempValueSet; 
    return ""; 
}