首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
28
问题
已知数组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
学硕统考专业
相关试题推荐
戊戌变法的思想启蒙作用主要表现在()
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
下列对春秋时期各国称霸的顺序描述错误的选项是()
在1919年巴黎和会上,日本代表对欧洲事务很少开口,故被称作“沉默的小伙伴”。日本“沉默”的主要原因是()。
唐朝时,从中国传到大食的手工技术是()
洋务运动时期,首批赴欧海军留学生派出的时间是()。
关于俄国工业革命的特点,正确的是()。①外国资本和技术在工业革命中起着重要的作用②工业革命发展极不平衡③企业资本有机构成低,技术落后④工业革命所需的资金主要来自对海外殖民地的掠夺
二战后的半个世纪中,资本主义各国经济史上的五个周期阶段。
洪武八年,朱元璋仿照元朝的办法,印造(),命令民间通行,形成了钱、钞并用的货币制度。
唐朝时期,每丁服徭役二十天,是为正役,国家若不需要其服役,则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准,交足二十天的数额以代役,称为()。
随机试题
A.1日常用量B.2日常用量C.3日常用量D.7日常用量E.15日常用量为门(急)诊癌症疼痛患者和中、重度慢性疼痛患者开具的麻醉药第一类精神药品控缓释制剂,每张处方不得超过
手术前护士收集的患者资料中,属于客观资料的是
预应力混凝土桥梁用塑料波纹管环刚度取其垂直方向变形为内径3%时所对应荷载值。()
运用实际锻炼法要求以理服人、以情动人、情理交融。()
根据以下资料,回答下列问题。2015年,中国创新指数为171.5,比上年增长8.4%,增幅为十年来最高。四个创新分领域21个指标中,有19个指标呈现增长态势,其中6个指标增速达到两位数以上,表明经济发展进人新常态情况下,我国在推进动能转换、结构转型和经济
美国的一个动物保护组织试图改变蝙蝠在人们心目中一直存在的恐怖形象。这个组织认为,蝙蝠之所以让人觉得可怕并遭到捕杀,仅仅是因为这些羞怯的动物在夜间表现得特别活跃。以下哪项如果为真,将对上述动物保护组织的观点构成最严重的质疑?
历史上俄罗斯的伊凡四世和英国的亨利八世都实行强有力的专制统治,请就二人政治举措的异同谈谈你的看法。
With2005fastbecoming"theyearofthenaturaldisaster",itistimetoreflectonhowengineering,scienceandtechnologyca
Whatwillfuturehistoriansrememberabouttheimpactofscience【C1】______thelastdecadeofthe20thcentury?Theywilln
A、Mostoftheman’sfriendsareathletes.B、Fewpeoplesharethewoman’sopinion.C、Themandoesn’tlooklikeasportsman.D、The
最新回复
(
0
)