免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 5613 | 回复: 30

[算法] 刚看到的一个排序算法题,大家讨论讨论。 [复制链接]

论坛徽章:
0
发表于 2006-12-28 16:33 |显示全部楼层
给你一个已经排好序的数组a,里面可能有重复元素,比如a[] = {1, 1, 1, 2, 3, 3, 4, 5, 5}。现在需要重新调整a里面的元素为a[] = {1, 2, 3, 4, 5, 1, 3, 5, 1},要求里面的每个子序列都是有序的,并且其中的元素唯一。另外,要求这样的子序列数最小,并且只能使用O(1)的辅助空间。

论坛徽章:
0
发表于 2006-12-28 17:25 |显示全部楼层
首先看有多少个最小的元素,有多少个就多少个序列

论坛徽章:
0
发表于 2006-12-28 17:30 |显示全部楼层
"要求这样的子序列数最小,并且只能使用O(1)的辅助空间"
这有什么用?

论坛徽章:
0
发表于 2006-12-28 17:33 |显示全部楼层
原帖由 sirius 于 2006-12-28 01:30 发表
"要求这样的子序列数最小,并且只能使用O(1)的辅助空间"
这有什么用?


面试题。

论坛徽章:
0
发表于 2006-12-28 18:22 |显示全部楼层
O(1)的辅助空间,那时间耗费太大,一个比较简单的就是求当前序列最长的子序列,并为了满足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}
红色表示当前正在寻找的子序列

论坛徽章:
0
发表于 2006-12-28 18:32 |显示全部楼层
原帖由 tyc611 于 2006-12-28 02:22 发表
O(1)的辅助空间,那时间耗费太大,一个比较简单的就是求当前序列最长的子序列,并为了满足O(1)空间,需要在找到子序列下一个元素时进行移动,比如:
{1, 1, 1, 2, 3, 3, 4, 5, 5}-->{1,[/colo ...


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

论坛徽章:
0
发表于 2006-12-28 18:35 |显示全部楼层
原帖由 emacsnw 于 2006-12-28 18:32 发表


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

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

论坛徽章:
0
发表于 2006-12-28 20:45 |显示全部楼层
原帖由 emacsnw 于 12/28/06 18:32 发表


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


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

论坛徽章:
0
发表于 2006-12-28 20:52 |显示全部楼层
能否照顾一下我这个数据结构盲
请说明一下什么是"O(1)的辅助空间"
3Q

论坛徽章:
0
发表于 2006-12-28 21:07 |显示全部楼层
我觉得这个题目是很有深意的
这个数组就像一个大公司
每个位置代表一个职位
那些重复的数字代表正在做着同样重复工作的员工
现在要把这个大公司拆分成若干小公司
小公司里大家各司其职没有重复
: )
发下自己的感触
并不是提供什么算法
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP