Doppelten Wert von Zeichenfolgenarray finden

Question

Ich fand einen doppelten Weg, den doppelten Wert vom Zeichenfolgenarray zu finden.

Erster Weg:

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 ""; 

    } 

Zweiter Weg:

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 ""; 
    } 

Beide Methoden richtig sind.

Meine Frage ist, welche eine beste Methode und warum? Oder gibt es eine andere Möglichkeit, den doppelten Wert eines Arrays herauszufinden?

Answer 1

Zweiter Weg.

Die Verwendung eines Sets ist für diesen Vorgang viel effizienter, da sValueSet.contains(tempValueSet) die Backing-Map (und damit Hash-Codes und schnelle Lookup-Zeiten) anstelle der vollständigen Iteration verwendet.

Answer 2

Beide Ansätze sind hinsichtlich der algorithmischen Komplexität fast gleich.

Die Komplexität des ersten Ansatzes ist O(N * N), wobei N die Länge des Arrays ist. Ich denke nicht, dass es notwendig ist zu erklären, warum, aber nur für den Fall, dass es ist - die verschachtelten Schleifen nehmen N * N Einheiten der Zeit, die die Komplexität gibt.

Was den zweiten Ansatz - ein HashSet ermöglicht es Ihnen, mit konstanter Komplexität (O(1)) zu suchen, weil die Suche auf dem Hash-Wert der String basiert. Man kann denken, dass dieser Ansatz effektiver ist, aber in Wirklichkeit ist es nicht so viel, weil wir den Einsatz Betrieb auf dem HashSet treffen müssen.

Hinzufügen zu HashSet ist von Komplexität O(N) (Worst-Case-Szenario). Für N String-Objekte könnten Sie N einfügen Operationen, die wiederum Komplexität von O(N * N) ergibt.

Also, um zusammenzufassen, sind beide Ansätze von ähnlichen Kosten. Ich würde jedoch die zweite bevorzugen, da sie etwas lesbarer ist.

Answer 3

Schöne Sache über Set ist, dass es add operation true zurückgibt, wenn dieser Satz das angegebene Element nicht bereits enthielt.

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); 
     } 
    } 
} 

Ausgang:

Duplizieren: ein

Answer 4

in Ihrem ersten Ansatz in der zweiten Schleife ich glaube, wenn Sie die Schleife Ausgangspunkt von j = 0 bis j ändern = i es wird es schneller machen. weil Sie zwei Werte zweimal

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

Dies scheint eine der schnellsten Wege zu sein, in O (n) ausgeführt wird, unter der Annahme eines fortgeführten Anschaffungs O (1) für HashSet.add plus erfordern Vergleich wird vermieden, nur eine Hash-Berechnung pro Iteration durch Weglassen der Verwendung von contains. Es ist wahr, dass String Hash-Code zwischenspeichert (dank Jonah), dieser Code verallgemeinert das Konzept des Weglassens 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 ""; 
}