首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
58
问题
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。
(1)给出算法的基本设计思想;
(2)根据设计思想,采用C或C++或Java语言表述算法,关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
用C语言算法描述如下: voild Adjust(int A[]){ //调整数组A,使得A的左边为负整数,右边为正整数 int i=1,j=n,temp; while(i<j)( while(A[i]<0&&i<j)i++; //A[i]为负整数时,i增1 while(A[j]>0&&i<j)j--; //A[j]为正整数时,j减1 if(i<<j){ Letup:A[i];A[i]:A[j];A[j]:temp;//A[i]为正整数、A[j]为负整数时,交换 i++: j--; } } } (3)算法的时间复杂度为O(n);算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kOxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1949年4月,中国人民解放军发起的重大战役是()。
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
汉高祖刘邦让陆贾分析秦失天下的原因,陆贾在他所著的()一书中,秦失天下的主要原因是“举措暴众而用刑太极故也”,并提出了轻徭薄赋的思想。
欧洲历史上第一部系统完备的法典是()。
在1900年巴黎代表大会上,第二国际围绕米勒兰入阁事件展开激烈争论,并通过“橡皮决议案”暂时防止了国际的分裂。这个“决议案”的起草人是()。
日本明治维新和中国戊戌变法一成一败的原因。
经济互助委员会
IEEE的802委员会已经标准化了很多种类的LAN,其中无线LAN标准是()。
随机试题
身处楼房的,发现火情不要盲目打开门窗,否则有可能引火人室。()
车床交换齿轮箱的中间齿轮等部位,一般用()润滑。
若=_____________.
我国常用的食品防腐剂有我国常用的食品漂白剂有
下列是资产负债组合管理的内容的有()。
发行债券筹资的优点包括()。
调低存贷款利率,我国适度从紧的货币政策将()。调低存款准备金率,是动用了准备金工具内容中的()。
企业拟进行一项投资,投资收益率的情况会随着市场情况的变化而发生变化,已知市场繁荣、一般和衰退的概率分别为0.3、0.5、0.,相应的投资收益率分别为20%、10%、-5%,则该项投资的投资收益率的标准差为()。
下列各项中,符合产品生命周期特征的有()。
当在滚动条内拖动滚动块时触发()。A.KeyUp事件B。KeyPress事件C.Scroll事件D.Change事件22.下面程序的输出结果是()。PrivateSubCommandlClick()Ch$=“
最新回复
(
0
)