已知数组A[1．．n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想； (2)根据设计思想，采用C或C++

admin2014-12-08 50

问题已知数组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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

1()中创造了“攻济打援”的战法，为后来的战役所效仿。

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

国民政府对日宣战的时间是()。

欧洲历史上第一部系统完备的法典是()。

红色割据和军阀割据的本质区别是()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：随着商业的发展，唐朝在货币和金融方面有一些重要的进步，以下表述全面的是()

隋唐五代时期是中国古代商品经济发展史上的一个重要阶段，种类多，交换规模大，交换方式多。试回答问题：我国银行最早的雏形是唐朝时期出现的()

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在Excel2010中，若某一单元格中输入的数值位数超过了11位，则该数值将______________显示。

叙述正确的处方制度是

猫，股骨干骨折7天后仍见患部肿胀、有热痛反应，骨折端不稳定，患肢不能负重，体温38．7℃。该猫处于骨折愈合过程的

以下各项中，()是对我国进出口药品管理正确的表述。

相对于发行债券和利用银行贷款购买设备而言，通过融资租赁方式取得设备的主要缺点是()。

属于陈鹤琴课程编制的十大原则的有()。

经济基础是社会一定发展阶段上的

除了测试程序之外，黑盒测试还适用于测试()阶段的软件文档。

ROM中的信息是()。