Fly me to the moon

the beauty of C++

wrong

    感谢Will同学指出的问题,我仔细思考后发现不只是代码的问题,算法思想上就有错了,我没有在每次交换后保持两个子序列的有序性,这样就无法保证i和j指向正确的位置,而如果想要保持子序列有序,虽然可以引入一个临时变量并通过交换实现,但算法复杂度就不是线性的了,所以结论是暂时没有可以简单实现的线性时间原地归并。事实上,有一些paper描述了很多线性时间原地归并的算法,但是复杂度都相当高,感兴趣的朋友可以自行google。
    为了不误导大家,把题目改了,至于下面的笔试题,希望牛人给予解答啊,谢谢。

---------------------------------------原文分割线-----------------------------------------------
    快要找工作了,现在在回顾一些算法和数据结构的知识,除了看书,争取每天挑一两道有趣的题目来练练手。本人没参加过ACM,解算法题的实力也相当菜鸟,但本人对于任何能够锻炼思维能力的题目都相当热衷,不怕做不出来,就怕不敢做,做多了,思考多了,总是有帮助的,呵呵,所以希望各位看到我的文章中有错误的地方请不吝赐教,在下感激不尽。
Share is happiness.

    今天的题目是在网上看到的,ms是一道baidu的笔试题:
    给定一个序列a[0...n-1]和一整数m,满足0<=m<=n-1,且a[0...m-1]和a[m...n-1]都为有序子序列,要求设计一个时间复杂度为O(N),空间复杂度为O(1)的算法,实现将这两个子序列合并为一个完整的有序序列a[0...n-1]。

    题意很简单,就是要设计一个线性时间的原地归并算法,我给出的思路:
    从左到右遍历数组,将当前未遍历元素中的最小值置换到它所应在的位置。这个简单的描述有点像选择排序,但选择排序O(N^2)的复杂度明显是不允许的,这里,利用两个子序列已有序的性质,我们可以设计更高效的O(N)算法:首先易知未遍历元素中的最小值必定是两个子序列的最小值中的更小者,将改值交换到它应在的位置;利用有序性,可以在遍历过程中分别记录两个子序列的当前最小元素的位置,这样就省去了选择排序中每次都要遍历剩余序列找出最小值的开销,每次遍历内部为常数次的比较和交换操作,所以整个算法的时间复杂度为O(N)。

posted on 2009-09-16 11:07 翼帆 阅读(454) 评论(2)  编辑 收藏 引用 所属分类: 算法

评论

# re: 线性时间原地归并[未登录] 2009-10-05 01:24 Will

程序有点问题:
比如{4,5,1,2,3}  回复  更多评论   

# re: wrong 2009-10-05 11:57 翼帆

谢谢Will  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜