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

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

admin2014-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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)