ソートされた 2 つの配列を効率的にマージするにはどうすればよいでしょうか?

ソートされた配列の効率的なマージ: 改良された方法

2 つのソートされた配列を 1 つのソートされた配列にマージするには、いくつかのプログラミング手法を使用できます。ただし、最も効率的で頻繁に推奨される手法の 1 つは次のとおりです。

このアルゴリズムは両方の配列を同時に反復処理し、現在の各インデックスの要素を比較し、小さい方の要素を出力配列に追加します。このプロセスは、アレイの 1 つが使い果たされるまで続きます。他の配列に残っている要素はすべて追加されます。

Java でのこのアルゴリズムの最適化された実装の例を次に示します。

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)
        answer[k++] = a[i] < b[j] ? a[i++] : b[j++];

    while (i < a.length)
        answer[k++] = a[i++];

    while (j < b.length)
        answer[k++] = b[j++];

    return answer;
}

このアプローチの時間計算量は O(n m )、ここで、n と m はそれぞれ配列 a と b の長さを表します。この改良されたバージョンでは、枯渇に関する不必要なチェックが排除され、効率的なマージのためにコンパクトな while ループ構造が採用されています。

以上がソートされた 2 つの配列を効率的にマージするにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。