1. 概要

このチュートリアルでは、特定のプログラミング言語ではなく、 2つの並べ替えられた配列を1つの並べ替えられた配列にマージし、理論的なアイデアに焦点を当て、擬似コード形式でソリューションを提供する方法について説明します。

最初に、問題を定義し、2つのソートされた配列をマージすることの意味を説明する例を提供します。

次に、問題を解決するための2つのアプローチについて説明します。

最後に、提供されているアプローチを比較し、両方が同じ複雑さを持っている場合について説明します。

2. 問題の定義

この問題により、サイズとサイズの2つの配列が得られます。 両方の配列は、値の昇順で並べ替えられます。

言い換えると：

   

   

その後、問題は、のすべての要素を含むサイズの結果の配列を計算するように要求します。 結果の配列もソートする必要があることに注意してください。 言い換えると：

   

アイデアをよりよく理解するために、次の例を見てみましょう。

例から、配列には要素があり、配列には要素があることがわかります。 したがって、結果の配列には要素が含まれます。

また、結果の配列には、およびのすべての要素が含まれます。 たとえば、配列には値が2回含まれています。 一方、値は1回だけ含まれます。 したがって、配列には値が3回含まれます。

また、結果の配列には、配列や。と同様に、昇順で並べ替えられたすべての要素が含まれます。

問題を十分に理解できたので、解決策を詳しく見ていきましょう。

3. 素朴なアプローチ

まず、素朴なアプローチについて説明しましょう。 その後、それを改善する方法を見ることができます。

単純なアプローチでは、配列とにすべての要素を追加するだけです。 次に、それを返す前にソートします。

その実装を見てください：

最初に、結果のサイズの配列を宣言します。 この配列は、問題に対する結果の答えを保持します。 また、ゼロで初期化します。これは、内に次の要素を追加するインデックスを指します。

その後、内部のすべての値を繰り返し処理し、結果の配列に追加します。 また、内のすべての値に対して同じ操作を実行します。

最後に、配列を並べ替えて、結果の回答として返します。

単純なアプローチの複雑さはです。ここで、は最初の配列内の要素の数であり、は2番目の配列内の要素の数です。

複雑な理由は、でソート操作を実行できるためです。

4. 2ポインターアプローチ

素朴なアプローチを改善しましょう。

4.1. 理論的アイデア

結果の配列に追加する必要がある最初の要素を見つけたいとします。 との内部で最小の要素である必要があります。

ただし、両方の配列とが並べ替えられているため、それぞれの最小要素が先頭にあります。 したがって、この値をに追加します。

ここで、この最小値を配列から削除したと想像して、問題についてもう一度考えてみましょう。 新しい最小の要素を見つけて、それに追加する必要があります。

その結果、この問題を解決するための一般的なアプローチを見つけることができます。 まず、2つのポインタとを定義します。 最初に、はの最初の要素を指し、はの最初の要素を指します。 各ステップで、最小値をに追加し、対応するポインターを1ステップ進めます。

に常に最小値を追加するため、に注意してください。 結果の配列は最終的にソートされます。

アイデアが明確になったので、このアプローチの実装にジャンプできます。

4.2. 実装

2ポインターアプローチの実装を見てみましょう。

まず、2つの変数をゼロで初期化します。 これらの変数は、必要な2つのポインターとして機能します。 したがって、は内部の現在のインデックスを指し、は内部の現在のインデックスを指します。

また、結果の回答を保持する配列を宣言します。 配列のサイズはである必要があることに注意してください。

次に、結果の配列内のすべてのインデックスを繰り返し処理します。 インデックスごとに、との間の最小値を格納し、対応するポインタを移動します。

それでも、配列のいずれかまたは最後に到達した場合を忘れてはなりません。 この場合、他の配列からの値を格納し、そのポインターを移動する必要があります。

最後に、結果の配列を返します。

2ポインターアプローチの複雑さはです。ここで、は最初の配列内の要素の数であり、は2番目の配列内の要素の数です。

5. 比較

一般的なケースでは、2ポインターアプローチの時間計算量が最も低くなります。 ただし、ナイーブなアプローチを2ポインターアプローチの1つと同じ複雑さで実装できる場合が1つあります。

内部のすべての要素が比較的小さい場合は、カウントソート手法を使用して結果の配列をソートできます。 この場合、カウントソートの複雑さは、です。ここで、は配列内の要素の数であり、は配列内の最大数です。

したがって、単純なアプローチの複雑さはになります。ここで、は最初の配列内の要素数、は2番目の配列内の要素数、は両方の配列内の最大値です。

その結果、の場合、単純なアプローチの複雑さはになります。

この複雑さは、2ポインターアプローチの複雑さに似ていることに注意してください。 結果の配列のサイズが。であるため、これ以上の複雑さを得ることができません。 したがって、最良の場合でも、それ以上の操作を実行せずに、要素を反復処理して1つずつ入力する必要があります。

6. 結論

このチュートリアルでは、2つの並べ替えられた配列を結果の並べ替えられた配列にマージする問題について説明しました。

最初に、例を使って問題について説明しました。

その後、問題を解決するために2つのアプローチを提供しました。 最初のアプローチは素朴なアプローチでしたが、2番目のアプローチは2ポインターアプローチでした。

最後に、両方のアプローチの比較を示し、ナイーブアプローチと2ポインターアプローチの両方が同じ複雑さに達する場合を示しました。