2つのソートされた配列を3番目のものにマージすることはO（n）で行うことができますか？

Question

ソートされた配列を3番目の並べ替え配列にマージしようとしていますが、 O(n)でこれを行う方法はありません。O(n*n) .Am間違っていますか？ O(n)にそれを行う方法はありますか？

編集：

実際の質問は少し異なります。

私は2つのソートスキップリストを持っていると私は 入力を変更せずに、新しいソートスキップリストにそれらをマージする（すなわち2つのスキップリスト）。

私が考えていた：

• はマージソートを使用して2つの配列をマージする二つの配列

• にリストを置く（これはO(n)ランタイムを取る）

• から新しいスキップリストを作成並べ替えられた配列.... //ランタイムについてはわかりません

アイデア？

よろしく

Answer 1

あなたは行く二つのループを維持し、あなたが第三配列にそれぞれ「側」から値を引くようにそれらのそれぞれの間で反転します。 arr1の値が現在のarr2より小さい場合は、arr3の値をarr3に入れるか、等しくなるか「もっと大きくなる」まで計算し、プロセスを反転してarr2から値を引き出します。そして、いずれかのソース配列に何も残らない限り、前後にバウンスしてください。

O（n + m）、別名O（n）になります。

Answer 2

ヒント：両方のリストの先頭の要素のみを考慮してください（処理時には[仮想的に削除する]）。

Answer 3

画像二つの配列互いに上下：

LIST1 = [1,2,6,10]我々は、左から始める場合

LIST2 = [-3,4,10-]

最も小さい値をとって3番目の配列に配置するたびに、アイテムを比較しながら右に向かって作業します。最小のアイテムを取り出したリストから、次のアイテムに移動します。

i=0,j=0 
list1[i] < list2[j] 
take 1 
i+=1 
2<3 
take 2 
i+=1 
3<6 
take 3 
j+=1 

など。

3番目の配列のための各要素を選択すると、一つだけの動きを取ったので、我々は最終的にマージされた配列[1,2,3、..]

を得るまで、それは基本的にですに）。

Answer 4

すでにソートされた配列には2つのインデックス変数を使用でき、ソート対象の配列にはもう1つのインデックス変数を使用でき、すべて0に初期化されます。 ソートされた配列で最後に到達していない間に、各反復で2つの尖った値を比較し、より高い（または低い、ソートに依存する）値を取り、インデックスをインクリメントして、ちょうど使用された。

最後に、完了していない配列を見て、残りの値を結合された配列に貼り付けます。

このように、O（n）を意味する値を1回だけ使用しています。

Answer 5

両方の入力リストが既にソートされている場合、マージはどのようにしてO（n * n）になりますか？自分で与えられたアルゴリズム（3ステップ）はO（n * n）ではなくO（n）です。各ステップはO（n）なので、全体的にはO（n）です。 big-Oは、アルゴリズムの最高位によって決定されます。あなたの宿題に取り組む前にbig-Oという概念を理解してください。

Answer 6

はい、実際にはO（n + m）となります。ここで、nとmは1番目と2番目の配列の長さです。

アルゴリズムは、1つのパスがマージと呼ばれる

疑似コード：基本的に

i, j, k = 0 // k is index for resulting array 
//maximum length of the resulting array can be n+m, 
//so it is always safe to malloc for such a length if you are in C or C++ 

while(i< len(array1) and j < len(array2)) 
    if (array1[i] == array2[j]) 
      result[k] = array1[i] 
      ++i, ++j, ++k 
    else if (array1[i] < array2[j]) 
      result[k] = array1[i] 
      ++i, ++k 
    else 
      result[k] = array2[j] 
      ++j, ++k 

//now one array might not be traversed all the way up 
if (i < len(array1)) 
     while(i != len(array1)) 
      result[k] = array1[i] 
      ++i, ++k 

else if (j < len(array2)) 
     while(j != len(array2)) 
      result[k] = array2[j] 
      ++j, ++k 

、一度に両方の配列を横断し、長さが異なる場合、大きいアレイウォン」すべての方法でトラバースされるので、大きな配列のすべての要素をの結果に追加するだけです。