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

セットを使用しない効率的な配列重複削除

プログラミングの課題によっては、事前に構築されたものを利用せずに配列から重複した値を削除する必要がある場合があります。 Set や HashSet などのデータ構造。検討できる最適化されたアプローチは次のとおりです。

提供された実装は配列に対して複数のパスを実行するため、時間の複雑さが非効率的になります。これを改善するには、次の 2 つの最適化を組み合わせて使用​​することを検討してください:

1。マーカー配列の使用:

元の配列の最大要素と同じサイズのマーカー配列を作成します。すべての要素を 0 に初期化します。元の配列内で要素が見つかったら、マーカー配列内の対応する位置を 1 に設定します。この方法では、マーカー配列をチェックするだけで、要素が重複しているかどうかを判断できます。

2.終了インデックス ポインターを使用する:

重複のない配列が計算されたインデックスを示す終了インデックス ポインターを維持します。重複が見つかった場合は、重複の後の要素を左にシフトし、それに応じて終了インデックスをデクリメントします。

これらの最適化を使用したコードの最適化バージョンは次のとおりです。

public static int[] removeDuplicates(int[] arr) {
    // Initialize the marker array with zeros
    int[] marker = new int[1000000];
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        // Check if the element is already marked as duplicate
        if (marker[arr[i]] == 1) {
            // If it's a duplicate, shift the elements after it to the left
            for (int j = i + 1; j < end; j++, i++) {
                arr[i] = arr[j];
            }
            end--;
            i--;
        } else {
            // If it's not a duplicate, mark it in the marker array
            marker[arr[i]] = 1;
        }
    }

    return arr;
}

この実装配列上の複数のパスを回避し、必要な要素のスワップの数を減らすことで、パフォーマンスが大幅に向上します。

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