Javaで2つのソートされた配列をマージする方法

投稿日: 2022-10-29 2022-10-29
タグ: Algorithms, Java, Java Array

1. 序章

このチュートリアルでは、2つの並べ替えられた配列を1つの並べ替えられた配列にマージする方法を学習します。

2. 問題

問題を理解しましょう。ソートされた配列が2つあり、それらを1つにマージしたいと思います。

3. アルゴリズム

問題を分析すると、マージソートのマージ操作を使用してこの問題を解決できることが非常に簡単にわかります。

長さfooLengthとbarLengthの2つのソートされた配列fooとbarがあるとします。次に、サイズ fooLength +barLengthの別の配列mergedを宣言できます。

次に、同じループで両方の配列をトラバースする必要があります。 fooPositionとbarPositionのそれぞれの現在のインデックス値を維持します。ループの特定の反復で、インデックスに小さい値の要素がある配列を取得し、そのインデックスを進めます。この要素は、merged配列の次の位置を占めます。

最後に、一方の配列からすべての要素を転送したら、残りの要素をもう一方の配列からmerged配列にコピーします。

次に、アルゴリズムをよりよく理解するために、写真でプロセスを見てみましょう。

ステップ1：

まず、両方の配列の要素を比較し、小さい方を選択します。

次に、first配列の位置をインクリメントします。

ステップ2：

ここでは、 second 配列の位置をインクリメントし、次の要素である8に移動します。

ステップ3：

この反復の終わりに、first配列のすべての要素をトラバースしました。

ステップ4：

このステップでは、残りのすべての要素をsecond配列からresultにコピーするだけです。

4. 実装

それを実装する方法を見てみましょう：

public static int[] merge(int[] foo, int[] bar) {

    int fooLength = foo.length;
    int barLength = bar.length;

    int[] merged = new int[fooLength + barLength];

    int fooPosition, barPosition, mergedPosition;
    fooPosition = barPosition = mergedPosition = 0;

    while(fooPosition < fooLength && barPosition < barLength) {
        if (foo[fooPosition] < bar[barPosition]) {
            merged[mergedPosition++] = foo[fooPosition++];
        } else {
            merged[mergedPosition++] = bar[barPosition++];
        }
    }

    while (fooPosition < fooLength) {
        merged[mergedPosition++] = foo[fooPosition++];
    }

    while (barPosition < barLength) {
        merged[mergedPosition++] = bar[barPosition++];
    }

    return merged;
}

そして、簡単なテストに進みましょう。

@Test
public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() {

    int[] foo = { 3, 7 };
    int[] bar = { 4, 8, 11 };
    int[] merged = { 3, 4, 7, 8, 11 };

    assertArrayEquals(merged, SortedArrays.merge(foo, bar));
}

5. 複雑

両方の配列をトラバースし、小さい方の要素を選択します。最後に、残りの要素をfooまたはbar配列からコピーします。 したがって、時間計算量はO（fooLength + barLength）になります。結果を得るために補助配列を使用しました。 したがって、スペースの複雑さもO（fooLength + barLength）です。

6. 結論

このチュートリアルでは、2つのソートされた配列を1つにマージする方法を学びました。

いつものように、このチュートリアルのソースコードは、GitHubのにあります。

getdocs

13036