首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
55
问题
已知数组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
学硕统考专业
相关试题推荐
两宋之交活跃于太行山一代,脸上刺有“赤心报国,誓杀金贼”的一支义军是()。
第一次鸦片战争期间,在镇江战死的满族副都统是()。
李大钊是在中国传播马克思主义最早的革命先驱者,下列李大钊的著作中,不属于揭开了我国马克思主义宣传的第一页的是()。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
社会主义教育运动,又称“四清”运动,下列不属于四清内容的是()。
晚清时期下列武装力量出现的先后顺序是
克里特文明的文字类型是()。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,该计算机为实现判优控制所需的控制线种类及数量分别为多少?
随机试题
A.毛细血管血压升高B.血浆胶体渗透压降低C.组织液胶体渗透压降低D.毛细血管壁通透性增高过敏反应时引起组织水肿的原因是
机体调节体液平衡主要通过的系统或器官是
某建设项目的建设期为2年,第一年贷款额为400万元,第二年贷款额800万元,贷款在年内均衡发生,贷款年利率为6%,建设期内不支付利息。计算建设期贷款利息为()。
常用的投标策略中,用于较长时期内,投标人没有在建的工程项目,如果再不得标,就难以维持生存的策略是()。
行业基准收益率表明了拟建项目()。
在资产总额和筹资组合都保持不变的情况下,如果固定资产增加,流动资产减少,则企业的风险和盈利()。
我国现存最早的《道藏》是《正统道藏》和《万历续道藏》。()
A、 B、 C、 D、 A
FiguringoutthecheapesttimetovisitDisneycanbea【K1】______(frighten)task,butonewomanfiguredoutaratherspecialw
HowtoDevelopanOutlineI.ApreliminaryoutlineA.Definition:a/an【T1】______listoftopicsandsubtopics【T1】______
最新回复
(
0
)