首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1..n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
54
问题
已知数组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
学硕统考专业
相关试题推荐
战国时期,楚国的()最为发达。
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
北魏建立和统一的时间分别是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
二战后世界经济发展变化迅速,这种变化主要表现在()①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美苏冷战为特征的两极格局④科学技术推动生产力发展更为迅速
周王室的两大官僚系统是()。
晚清时期下列武装力量出现的先后顺序是()。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
下列关于1929~1933年经济危机的描述,错误的有()。
洪武八年。朱元璋仿照元朝的办法,印造(),命令民间通行。形成了钱、钞并用的货币制度。
随机试题
直接影响到统一战线和武装斗争这两大法宝作用发挥的是()
月明星稀,乌鹊南飞。绕树三匝,何枝可依?山不厌高,海不厌深。周公吐哺,天下归心。将“山不厌高,海不厌深。周公吐哺,天下归心”译成现代汉语。
下列乳腺癌的病理类型中,预后较好的是
流行性脑脊髓膜炎临床分期为
男,47岁,进食油煎鸡蛋后出现右上腹剧痛,并放射至右肩胛区,伴畏寒、发热,应考虑的诊断为
我国目前的股权投资基金实行()。
人民检察院对公安机关及其人民警察的监督主要是在各种诉讼活动中通过法定的程序实现的。()
社会主义法是()的体现。
简述教育研究的基本原则。
查询单价在600元以上的主机板和硬盘的正确SQL命令是( )。
最新回复
(
0
)