文字列配列から重複する値を見つける

Question

文字列配列から重複する値を見つける方法が2つ見つかりました。

最初の方法：

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

    } 

第二の方法：

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

どちらの方法が適切です。

私の質問は、どの1つの最良の方法で、なぜですか？または、重複した値から配列を見つける他の最良の方法はありますか？

Answer 1

第2の方法。

sValueSet.contains(tempValueSet)は完全に反復するのではなく、バッキングマップ（したがってハッシュコードと高速検索時間）を使用するため、この操作の方がはるかに効率的です。

Answer 2

どちらの方法も、アルゴリズムの複雑さに関してはほとんど同じです。

最初のアプローチの複雑さはO(N * N)であり、Nは配列の長さです。理由を説明する必要はないと思っていますが、その場合にはネストされたループはN * N単位の時間がかかり、複雑さが増します。

第2のアプローチとして、HashSetを使用すると、検索はハッシュ値Stringに基づいているため、一定の複雑さ（O(1)）で検索することができます。このアプローチはより効果的だと考えることができますが、HashSetでの挿入の操作が発生する必要があるため、それほど多くはありません。

HashSetへの追加は、複雑さがO(N)（最悪の場合のシナリオ）です。 N Stringオブジェクトの場合、Nの挿入操作が発生する可能性があります。その場合も、O(N * N)という複雑さがあります。

したがって、要約すると、どちらのアプローチも同様の費用です。私はもう少し読みやすいので、2番目を好むだろう。

Answer 3

このセットにはまだ指定された要素が含まれていない場合、add operationは trueを返します。

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

出力：

重複：あなたは= 0 jにjからループ開始点を変更した場合、私は信じている第二のループでは、あなたの最初のアプローチで

Answer 4

=私にそれをそれはより速くなります。あなたは2つの値を比較しないようになるので、二回

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

これはHashSet.addため償却O（1）を仮定して、O（n）の中で実行されている、最速のアプローチの一つであると思われる、プラスのみ必要containsの使用を省略することによって、反復ごとに1つのハッシュ計算を実行します。 ストリングが（ジョナのおかげで）ハッシュコードをキャッシュしていることは事実です。このコードは、 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 ""; 
}