Java 配列内で重複する整数を効率的に見つけるにはどうすればよいですか?

Java 配列内の重複の検索

問題

整数配列があり、重複を効率的に特定したいと考えています。要素の各ペアを比較しようとする最初のコードは、重複が存在しない場合に正確に検出できません。

問題

コードの欠陥は、初期化される重複フラグに依存していることにあります。すべての場合に false になります。重複が見つからない場合でも、ループは対角要素をチェックするとき (つまり、 j == k のとき) に重複を true に設定します。

より微妙な解決策

これを解決するには、次のことを確認してください。重複フラグは、実際の重複が見つかった場合にのみ true に設定されます。これは、 j == k の場合に zipcodeList[j] とそれ自体の比較を省略することで実現できます。

修正されたコードは次のとおりです。

duplicates = false;
for (int j = 0; j < zipcodeList.length; j++) {
    for (int k = 0; k < zipcodeList.length; k++) {
        if (k != j && zipcodeList[k] == zipcodeList[j]) {
            duplicates = true;
        }
    }
}

より高速なアプローチ

上記の解決策の実行時の複雑さは O(n²) です。ここで、n は配列内の要素の数です。大規模な配列の場合、このアプローチは非効率的になる可能性があります。

重複を検出するより効率的な方法は、ハッシュベースのアプローチを活用し、時間の複雑さを O(n) に減らすことです。 HashSet を使用した例を次に示します。

boolean duplicates(int[] zipcodeList) {
    Set<Integer> lump = new HashSet<>();
    for (int zipcode : zipcodeList) {
        if (lump.contains(zipcode)) {
            return true;
        }
        lump.add(zipcode);
    }
    return false;
}

あるいは、boolean[] 配列 (ビットマップ) を使用して、以前に検出された要素を追跡し、要素が次の場合に重複を true に設定することにより、O(n) ソリューションを実現できます。

結論

入力配列のサイズと重複の頻度に応じて、アプローチの選択は、効率を最適化するように調整する必要があります。

以上がJava 配列内で重複する整数を効率的に見つけるにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。