首页 > 试题广场 >

数列中所有的负整数调至前半部分,正整数调至后半部分。

[问答题]

已知一个数列A,其中包含若干个任意排列的正整数和负整数。试设计一个算法,将数列中所有的负整数调至前半部分,正整数调至后半部分。

要求:算法的时间复杂度为O(n),空间复杂度为0(1)。其中,n为数列包含的整数个数。

假设存放数列A的数据类型定义为:

typedef struct{          //存放数列A的数据类型

    int data[MAXSIZE];   //存放数列数据的连续存储空间

    int size;            //当前数列包含的数据个数

}SqList;

其中,MAXSIZE是数组data长度的宏

算法的函数原型定义为:

void adjust(SqList &L)

/*链接:https://www.nowcoder.com/questionTerminal/d41e732d29c84549bb08d5825b295713
来源:牛客网

要求:算法的时间复杂度为O(n),空间复杂度为0(1)。其中,n为数列包含的整数个数。

假设存放数列A的数据类型定义为:

typedef struct{          //存放数列A的数据类型

    int data[MAXSIZE];   //存放数列数据的连续存储空间

    int size;            //当前数列包含的数据个数

}SqList;

其中,MAXSIZE是数组data长度的宏

算法的函数原型定义为:
*/
void adjust(SqList &L) {
    int i=0,j=L.size-1;
    while(i<j){
        while(L.data>0&&i<j) j--;
        while(L.data<0&&i<j) i++;
        if(i<j){
            int temp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = temp;
        }
    }
    return ;
}


发表于 2020-11-22 15:14:16 回复(0)
快排一趟循环即可
发表于 2019-08-21 06:51:56 回复(0)