数组合并问题!
数组[1,n]的两个子数组[1,k]和[k+1,n]都已经排好序.
现在要把它们合并,使整个数组都是有序的.
要求只用O(n)的时间和O(1)的空间
问题点数：20、回复次数：4Top
1 楼zimogaoshou（自摸高手）回复于 2006-03-02 23:56:47 得分 0
顶Top
2 楼zimogaoshou（自摸高手）回复于 2006-03-06 05:08:41 得分 0
怎么没人帮忙? 分数太少了还是题目太简单了?Top
3 楼SK_MadFrog（平凡但不平庸的人）回复于 2006-03-06 15:35:08 得分 0
我的思路是这样的,不知道是否满足要求:
显然遍历数组的指针不允许回溯,定义两个指示器i和j,和一个临时变量temp,开始令i=1和j=k;
比较a[i]和a[j],temp存贮较小值,较大值指示器加1,一直到i=k或j=n为止.Top
4 楼mmmcd（超超）回复于 2006-03-06 19:05:50 得分 0
要是合并过程中保证有序，需要插入操作；而在数组中，这是最费时的。（插入排序O(n^2)）
要是仅仅交换元素，又难保证有序。
这个矛盾比较难解决。Top
