有限制排序整數

如果我們有一個整數數組，那麼如果每步僅允許的操作是：將元素移動到極限值，我們如何確定對它們進行排序所需的最小步數（按升序排列）？ E.g如果我們有有限制排序整數

7 8 9 11 1 10

然後在第一步驟一個可以移動11右端和在第二步驟中移動1至左端，得到1 7 8 9 10 11。因此，總步驟= 2 這裏可以使用氣泡排序嗎？但是最壞的情況複雜度將是O（n^2）。那麼我們怎樣才能更高效地工作呢？謝謝。

來源

2012-04-10 pranay

你能澄清這個問題嗎？當你說清單時，你的意思是一個鏈表還是你的意思是一個數組？如果它不是鏈表，我對有限的操作集有點困惑。如果它是一個鏈表，你可以修改運行在平均情況下O（nlgn）時間的quicksort。

來源

2012-04-10 03:49:19 vpiTriumph

它的一個數組......更新 – pranay 2012-04-10 05:36:49

基本上你提到的數據結構是一個鏈表。對於鏈接列表，您可以使用快速排序或合併排序（O（nlogn））。

來源

2012-04-10 03:50:28 ElKamina

這是一個解決方案，它需要O（n log n）時間，O（n）輔助空間和正好n個MoveToFront操作。

鑑於輸入陣列，A，製作一個第二陣列，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]

然後降序每對的值的順序排序乙.. 。

(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)

我想你可以想辦法將這些陣列使用超過n MoveToFront /後退操作較少的排序，但我不認爲你可以找到那些小於O（n log n）時間。但是，如果這些操作很慢，那麼可能需要使用花費更多時間進行規劃的算法，以便您可以執行更少的操作。

來源

2012-04-10 07:00:40

這並不能解決問題，因爲作者的例子返回2，但你似乎返回5.我錯過了什麼嗎？ – Archeg 2012-04-10 07:13:24

作者問我們是否可以比n^2 MoveToFront/Back操作更有效地對數組進行排序。我在這裏展示了，如果我們用O（n log n）時間來做這件事，我們可以在n MoveToFront/Back操作中做到這一點，並且我假設，如果不超過O（n log n）時間，我們不可能做得更好。 – 2012-04-10 07:19:55

不錯。這讓我想起了http://www.spoj.pl/problems/YODANESS/，我使用了類似的樹。（雖然我可以使用範圍樹） – 2012-04-10 12:56:40

這聽起來不像我這樣的排序問題。你只需要找出你需要做多少動作，但是你不需要對數組進行排序。我敢打賭，可以做得比O更快（n日誌n）

我建議這樣的解決方案：只是計算有多少a [i]> a [i - 1]。這將是你的結果。

論點：如果你有一個[i]> a [i-1]，這意味着，無論是[i]還是[i-1]都不在他們的位置。這樣你就可以：

1）移動一個[I-1]到陣列

2）的開始移動[I]到數組的末尾。

Upd。你需要定義你正在移動哪一個[i]或[i-1]，就像你的數組的例子一樣：7 8 9 11 1 10你有兩個比較，顯示什麼不到位：11 > 1和11> 10.因此，這就是動態編程的任務。但它仍然比O（n log n）更快

來源

2012-04-10 07:29:24 Archeg

有限制排序整數

回答

相關問題