剛看到的一個排序算法題，大家討論討論。

emacsnw

給你一個已經(jīng)排好序的數(shù)組a，里面可能有重復(fù)元素，比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。現(xiàn)在需要重新調(diào)整a里面的元素為a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1}，要求里面的每個子序列都是有序的，并且其中的元素唯一。另外，要求這樣的子序列數(shù)最小，并且只能使用O(1)的輔助空間。

hake2000

首先看有多少個最小的元素，有多少個就多少個序列

sirius

"要求這樣的子序列數(shù)最小，并且只能使用O(1)的輔助空間"
這有什么用?

emacsnw

原帖由 sirius 于 2006-12-28 01:30 發(fā)表
"要求這樣的子序列數(shù)最小，并且只能使用O(1)的輔助空間"
這有什么用?

面試題。

tyc611

O(1)的輔助空間，那時間耗費太大，一個比較簡單的就是求當前序列最長的子序列，并為了滿足Ｏ（１）空間，需要在找到子序列下一個元素時進行移動，比如：
{1, 1, 1, 2, 3, 3, 4, 5, 5}-->{1,1, 1, 2, 3, 3, 4, 5, 5}-->{1, 2, 1, 1,  3, 3, 4, 5, 5}
紅色表示當前正在尋找的子序列

emacsnw

原帖由 tyc611 于 2006-12-28 02:22 發(fā)表
O(1)的輔助空間，那時間耗費太大，一個比較簡單的就是求當前序列最長的子序列，并為了滿足Ｏ（１）空間，需要在找到子序列下一個元素時進行移動，比如：
{1, 1, 1, 2, 3, 3, 4, 5, 5}-->{1,[/colo ...

這是O(n^2)的，移動數(shù)組元素的代價很大。我想可能有更快一些的算法。

tyc611

原帖由 emacsnw 于 2006-12-28 18:32 發(fā)表


這是O(n^2)的，移動數(shù)組元素的代價很大。我想可能有更快一些的算法。

因為你輔助空間為O(1)，要記錄當前子序列，還要記錄剩下的，只能移動
好的方法沒想到

ArXoR

原帖由 emacsnw 于 12/28/06 18:32 發(fā)表


這是O(n^2)的，移動數(shù)組元素的代價很大。我想可能有更快一些的算法。

如果輔助空間要求O(1)的話, 我懷疑是否存在復(fù)雜度比O(n^2)還低的算法.

bleem1998

能否照顧一下我這個數(shù)據(jù)結(jié)構(gòu)盲
請說明一下什么是"O(1)的輔助空間"
3Q

bleem1998

我覺得這個題目是很有深意的
這個數(shù)組就像一個大公司
每個位置代表一個職位
那些重復(fù)的數(shù)字代表正在做著同樣重復(fù)工作的員工
現(xiàn)在要把這個大公司拆分成若干小公司
小公司里大家各司其職沒有重復(fù)
： ）
發(fā)下自己的感觸
并不是提供什么算法