【求一个算法设数组A[1..2n]中存放有n个负数和n个正数,且随机存放.现要求按负数正数相间存放.请写出实现此要求的算法.算法要求:不能使用额外的存储空间,但可使用少量工作单元,算法的时间】
1人问答
问题描述：
求一个算法
设数组A[1..2n]中存放有n个负数和n个正数,且随机存放.现要求按负数正数相间存放.请写出实现此要求的算法.算法要求:不能使用额外的存储空间,但可使用少量工作单元,算法的时间复杂度应为O(n).
黄云平回答：
相间存放,说明如果所有负数在奇数位置上,则所有正数在偶数位置上,反之亦然.假设把所有负数都放奇数位置上,所有正数都放偶数位置上,则A[0],A[2],...,A[2n-2]位置应该都存放负数,A[1],A[3],...,A[2n-1]位置上应该存放正数.可以设计两个索引forward和back,初始分别执行第一个位置和最后一个位置,forward每次都递增2,back每次都递减2,直到forward所指位置的元素为正数,back所指元素为负数,然后交换forward和back所指元素.一直到遍历完数组中的所有元素.
参考程序：
voidarrange(inta[],intn)
{
intforwad,back;
forward=0;
back=2*n-1;
while(forward0)
{
while(forward0)
back-=2;
if(back>0)
{
inttemp;
temp=a[forward];
a[forward]=a[back];
a[back]=temp;
}
}
}
其它推荐
其它推荐
最新更新
精品分类
优秀其它推荐
热门其它
邮箱： 