java - 2つの並べ替えられた配列を、3番目の配列を使用せずに並べ替えられた配列にマージする方法

Question

昇順で2つの並べ替えられた配列があり、そのうちの1つが両方の配列のすべての要素を収容するための余分なスペースを保持している場合、2つの並べ替えられた配列をマージして、結果の配列も3番目の配列を作成せずに昇順で並べ替えられます。

私はほとんどマージ用のプログラムを作成しましたが、3番目の配列を使用しました。

Answer 1

効率の問題がない場合は、1 つの配列を他の配列の末尾に追加するだけです。次に、この連結配列をソートします。

Answer 2

1 つのアプローチは次のようになります。

1. 小さい方の配列から最初の要素を取得し、大きい方の配列でその位置 (たとえば n 番目の位置) を見つけます。

2. 小さい方の配列から 2 番目の要素を取得し、最初からではなく大きい方の配列でその位置を n 番目以降から見つけます。

3. 小さな配列から 3 番目の要素を取得し、小さな配列が使い果たされるまでこのプロセスを繰り返します。

複雑さの比較

1.その最良のケースの複雑さは、より小さい配列のサイズと同じくらい低いです。ただし、最悪の場合は、小さい配列のサイズ * 大きい配列のサイズです。

2. コレクション API のユーティリティ ソート メソッド、つまり Collection.sort() または Arrays.sort() を使用する場合、それらの複雑さはすべての場合でO(nlogn)になります。ここで、n は各配列のサイズの合計です。メソッドはマージソートを使用します。

Answer 3

public static int[] merge(int[] a, int[] b) {    
    int a_size = a.size();
    for(int i=0; i<b.size();i++ ) {
        a[a_size]= b[i];
        a_size++;
    } 
    Arrays.sort(a);
}