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

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

admin2014-12-08  46
问题 已知数组A[1……n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
    (1)给出算法的基本设计思想；
    (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释；
    (3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案(1)算法的基本设计思想如解析所述。 (2)用C语言算法描述如下： void Adjust(int A[]){ ／／调整数组A，使得A的左边为负整数，右边为正整数 int i=1，j=n，temp； while(i0&&i
解析 本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值，然后分别从数组前端查找正整数和从数组末端查找负整数，找到后进行交换，直到上、下界相遇。
    具体做法是：设置两个指示器i和j，其中i=1，j=n；当A为正整数，A[j]为负整数时，A和A[j]交换；否则，A为负整数时，则i++；A[j]为正整数时，则j--。这样，
    可使算法的时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/44xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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