Question

2个递增有序数组的长度和为N.设计算法合并为一个递增有序数组.要求时间复杂度为O(n),空间复杂度为O(1).

提供思路好的可得50.提供完整解决方案则再加200分
谢谢回答,请注意要求:-).时间复杂度和空间复杂度

也谢谢2楼的.空间复杂度的定义就是程序执行所需要的存储空间大小啊.怎么能不计算呢?

我的题目没说清楚.应该是这两个有序序列合起来是一个长度为N的数组.

排序结果就存在这个数组里.

Answer 1

再加200分!

合并后放在哪里？
假如放在第一个数组或第二个数组里面，那么要保证这个数组够大！
假如放在第三个数组里，那么，它不算在空间复杂度里面里。
因为它不是辅助空间，而是存放结果的空间。

其实，这是个很简单的问题！！！

void main()
{
const int N1=3,N2=7,N=N1+N2; //编译器版本太低的话，把它们改为宏定义
int a1[N1]={1,2,7},a2[N2]={0,3,4,5,6,8,9},a3[N]={0};
int i1,i2,i;

for(i1=0,i2=0,i=0;i1<N1 && i2<N2 && i<N;)
{
if(a1[i1]<a2[i2])
{
a3[i++]=a1[i1++];
}
else
{
a3[i++]=a2[i2++];
}
}
if(i1<N1)
{
for(;i1<N1 && i2<N2 && i<N;)
{
a3[i++]=a1[i1++];
}
}
else
{
for(;i1<N1 && i2<N2 && i<N;)
{
a3[i++]=a2[i2++];
}
}
}

Answer 2

假设2个数组为A、B，把A的长度扩充到N，从B数组的第一个元素开始取值，然后跟A中的元素比较，插入到A数组中合适的位置。

Answer 3

我也想知道合并后放在哪里．．