刚看到的一个排序算法题，大家讨论讨论。

emacsnw

给你一个已经排好序的数组a，里面可能有重复元素，比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1}，要求里面的每个子序列都是有序的，并且其中的元素唯一。另外，要求这样的子序列数最小，并且只能使用O(1)的辅助空间。

hake2000

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

sirius

"要求这样的子序列数最小，并且只能使用O(1)的辅助空间"
这有什么用?

emacsnw

原帖由 sirius 于 2006-12-28 01:30 发表
"要求这样的子序列数最小，并且只能使用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 发表
O(1)的辅助空间，那时间耗费太大，一个比较简单的就是求当前序列最长的子序列，并为了满足Ｏ（１）空间，需要在找到子序列下一个元素时进行移动，比如：
{1, 1, 1, 2, 3, 3, 4, 5, 5}-->{1,[/colo ...

这是O(n^2)的，移动数组元素的代价很大。我想可能有更快一些的算法。

tyc611

原帖由 emacsnw 于 2006-12-28 18:32 发表


这是O(n^2)的，移动数组元素的代价很大。我想可能有更快一些的算法。

因为你辅助空间为O(1)，要记录当前子序列，还要记录剩下的，只能移动
好的方法没想到

ArXoR

原帖由 emacsnw 于 12/28/06 18:32 发表


这是O(n^2)的，移动数组元素的代价很大。我想可能有更快一些的算法。

如果辅助空间要求O(1)的话, 我怀疑是否存在复杂度比O(n^2)还低的算法.

bleem1998

能否照顾一下我这个数据结构盲
请说明一下什么是"O(1)的辅助空间"
3Q

bleem1998

我觉得这个题目是很有深意的
这个数组就像一个大公司
每个位置代表一个职位
那些重复的数字代表正在做着同样重复工作的员工
现在要把这个大公司拆分成若干小公司
小公司里大家各司其职没有重复
： ）
发下自己的感触
并不是提供什么算法