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

admin2014-12-08  41

问题 已知数组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
0

最新回复(0)