3

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

編集 ：

実際、質問は少し異なります：

2つのソートされたスキップリストがあり、入力（つまり、2つのスキップリスト）を変更せずに、それらを新しいソートされたスキップリストにマージしたいと思います。

私は考えていました：

  • リストを2つの配列に配置します

  • MergeSortを使用して2つの配列をマージします（これにはO(n)実行時間がかかります）

  • ソートされた配列から新しいスキップリストを作成します....//その実行時間についてはわかりません

何か案は ？

よろしく

4

6 に答える 6

10

2 つのループを続けて、それぞれの「サイド」から 3 番目の配列に値をプルしながら、それぞれを切り替えます。arr1 の値が現在の arr2 よりも小さい場合は、arr1 の値を arr3 に詰め込んで、同等になるか「大きく」し、プロセスを反転して arr2 から値を引き出し始めます。そして、どちらのソース配列にも何も残らなくなるまで、前後に跳ね続けます。

O(n+m)、別名 O(n) になります。

于 2012-05-01T04:46:13.553 に答える
9

2 つの配列を上下に並べた図:

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

等..

最終的にマージされた配列 [1,2,3,..] が得られるまで

3 番目の配列の各要素の選択は 1 回の移動で済むため、基本的には O(N) です。

于 2012-05-01T04:47:52.840 に答える
1

既にソートされた配列に 2 つのインデックス変数を使用し、ソートされる配列に別の 1 つを使用して、すべて 0 に初期化できます。ここで、ソートされた配列のいずれも最後まで到達していない間に、それぞれの 2 つの指定された値を比較します。繰り返し、より高い（またはより低い、ソートに応じて）値を取り、使用したばかりの値を指すインデックスをインクリメントします。

最後に、完成していない配列を調べて、残りの値をマージされた配列に貼り付けます。

そうすれば、値を 1 回だけ通過することになります。つまり、O(n) です。

于 2012-05-01T04:52:08.310 に答える
0

ヒント: 両方のリストの head 要素のみを考慮してください (処理時にそれらを [仮想的に] 削除します)。

于 2012-05-01T04:47:03.083 に答える
0

はい、できます。実際にはO(n + m)になります。ここで、n と m は最初と 2 番目の配列の長さです。

アルゴリズムはワンパスマージと呼ばれます

擬似コード:

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

基本的に、両方の配列を同時にトラバースします。長さが異なる場合、大きい方の配列は最後までトラバースされないため、大きい方の配列のすべての要素を結果に追加するだけです。

于 2016-12-24T03:10:09.223 に答える
0

両方の入力リストが既にソートされている場合、マージはどのようにして O(n*n) になるのでしょうか? 自分で指定したアルゴリズム (3 つのステップ) は、間違いなく O(n*n) ではなく O(n) です。各ステップは O(n) なので、全体としては O(n) です。big-O は、アルゴリズムの最高次数によって決定されます。宿題に取り組む前に、big-O の概念を必ず理解してください。

于 2012-05-01T09:59:54.493 に答える