セットを使用せずに配列から重複を効率的に削除するにはどうすればよいですか?

設定に頼らずに配列から重複を効率的に削除する

配列から重複要素を削除するためのカスタマイズされたソリューションを作成することに努めました。しかし、パフォーマンスのボトルネックが発生しています。この実装を最適化するために、アプローチの欠点を分析し、代替戦略を提案します。

アルゴリズムの分析

アルゴリズムは、それぞれを比較して重複を検索しようとします。要素と後続のすべての要素。この徹底的な比較により、時間計算量は O(n^2) になります。大規模な配列の場合、この戦略は非常に非効率になる可能性があります。

最適化されたアプローチ

パフォーマンスを大幅に向上させるために、次の最適化を検討できます:

1. ハッシュ マップの利用: 保存するハッシュ マップを実装します。反復中に遭遇した固有の要素。各要素が配列に追加されるときに、その要素がハッシュ マップにキーとしてすでに存在するかどうかを確認します。そうでない場合は追加してください。このアプローチにより、効率的な定数時間ルックアップ操作が可能になり、時間の複雑さが O(n) に軽減されます。
2. フィルタリング前の並べ替え: 配列を昇順に並べ替えます。これで、重複した要素が互いに隣接するようになります。ソートされた配列を反復処理し、隣接する重複を削除すると、線形時間 O(n) アルゴリズムが得られます。

代替ソリューション

一方、前述の最適化は可能です。アルゴリズムのパフォーマンスを向上させるには、他の確立されたものを考慮することもできますテクニック:

• Set コレクション: Set の使用を避ける必要があるため、このオプションについては詳しく説明しません。
• ソートされたコレクションの使用: フィルタリング前の並べ替えと同様に、TreeSet や NavigableSet などの並べ替えられたコレクションを利用します。ソートされた順序が自動的に維持され、効率的な要素の取得が可能になるため、複雑さは O(n log n) になります。

実装

最適化されたアプローチに基づいて、ハッシュ マップを利用したアルゴリズムの修正バージョンは次のようになります:

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

以上がセットを使用せずに配列から重複を効率的に削除するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。