3

整数の配列がある場合、ステップごとに許可される操作が次の場合、それらを（昇順で）並べ替えるのに必要な最小ステップをどのように決定できますか？要素をいずれかの極値に移動しますか？たとえば、

7 8 9 11 1 10

次に、最初のステップで11を右端に移動し、2番目のステップで1を左端に移動して1 7 8 91011を取得します。したがって、合計ステップ=2 ここでバブルソートを適用できますか？しかし、最悪の場合の複雑さはO（n ^ 2）になります。では、どうすればもっと効率的にできるでしょうか？ありがとう。

4

4 に答える 4

2

これは、O(n log n) 時間、O(n) 補助スペース、正確に n 回の MoveToFront 操作を必要とするソリューションです。

入力配列 A を指定して、次のように、値/インデックスのペアで 2 番目の配列 B を作成します...

7 8 9 11 1 10  ->  (7 0) (8 1) (9 2) (11 3) (1 4) (10 5)
[this step takes O(n) time and O(n) space]

次に、各ペアの値の降順で B を並べ替えます...

(7 0) (8 1) (9 2) (11 3) (1 4) (10 5) -> (11 3) (10 5) (9 2) (8 1) (7 0) (1 4)
[this step takes O(n log n) time]

二分探索木 T を準備します。

B の各要素に対して、次の操作を行います...

Let I be the index of this element.
Let V be the sum of I and the number of elements in T that are greater than I.
Do a MoveToFront operation on the Vth element of A.
Add I to T.
[Both of the operations on T take O(log n) time]

サンプル配列で動作するこのアルゴリズムは次のとおりです

(11 3)
    I := 3
    V := 3 + 0 = 3
    MoveToFront(3): 7 8 9 11 1 10  ->  11 7 8 9 1 10
    T: ()  ->  (3)

(10 5)
    I := 5
    V := 5 + 0 = 5
    MoveToFront(5): 11 7 8 9 1 10  ->  10 11 7 8 9 1
    T: (3)  ->  (3 5)

(9 2)
    I := 2
    V := 2 + 2 = 4
    MoveToFront(4): 10 11 7 8 9 1  ->  9 10 11 7 8 1
    T: (3 5)  ->  (2 3 5)

(8 1)
    I := 1
    V := 1 + 3 = 4
    MoveToFront(4): 9 10 11 7 8 1  ->  8 9 10 11 7 1
    T: (2 3 5)  ->  (1 2 3 5)

(7 0)
    I := 0
    V := 0 + 4 = 4
    MoveToFront(4): 8 9 10 11 7 1  ->  7 8 9 10 11 1
    T: (1 2 3 5)  ->  (0 1 2 3 5)

(1 4)
    I := 4
    V := 4 + 1 = 5
    MoveToFront(5): 7 8 9 10 11 1  ->  1 7 8 9 10 11
    T: (0 1 2 3 5)  ->  (0 1 2 3 4 5)

MoveToFront/Back 操作を n 回未満使用するこれらの配列を並べ替える方法を見つけることができると思いますが、O(n log n) 時間未満でそれらを見つけることはできないと思います。ただし、これらの操作が遅い場合は、計画に時間がかかるアルゴリズムを使用して、それらの操作を少なくすることをお勧めします。

于 2012-04-10T07:00:40.200 に答える
0

この問題を少し明確にしていただけますか？リストと言うとき、リンクされたリストを意味しますか、それとも配列を意味しますか? リンクされたリストでないと、限られた操作セットに少し戸惑います。それがリンクされたリストである場合、おそらく平均ケース O(nlgn) 時間で実行されるクイックソートを変更できます。

于 2012-04-10T03:49:19.967 に答える
0

それはソートの問題のようには思えません。必要な動きの数を見つけるだけで済みますが、配列を並べ替える必要はありません。O(n log n) よりも高速に実行できるはずです。

私はそのような解決策を提案します: a[i] > a[i - 1] の数を数えるだけです。そしてそれがあなたの結果になります。

引数: a[i] > a[i-1] の場合は、a[i] または a[i-1] がその場所にないことを意味します。だからあなたはできる：

1) a[i-1] を配列の先頭に移動する

2) a[i] を配列の末尾に移動します。

更新。配列の例のように、移動する a[i] または a[i-1] を定義する必要があります: 7 8 9 11 1 10 2 つの比較があり、何が適切でないかを示しています: 11 > 1 と 11 > 10 です。これは明らかに動的計画法のタスクです。しかし、それはまだ O(n log n) よりも高速です

于 2012-04-10T07:29:24.493 に答える
0

基本的に、言及しているデータ構造はリンクされたリストです。リンクされたリストの場合、クイックソートまたはマージソート ( O(nlogn) ) を使用できます。

于 2012-04-10T03:50:28.653 に答える