数据结构 习题答案

若一个线性表L采用顺序存储结构存储,其中所有元素为整数,设计一个算法,将所有小于0的元素面前,要求算法的时间复杂度为O(n),空间复杂度为O(l)

3个回答

 #include <stdio.h>

void swp(int& a, int& b)
{
    int c = a;
    a = b;
    b = c;
}

int main()
{
    int z = 0, i = 0;
    int data[] = {2,-1,0,5,-3,8,-2,-9,0,8};
    for (i = 0; i < 10; i++)
    {
        if (data[i] < 0)
        {
            swp(data[i], data[z]);
            z++;
        }
    }
    for (i = 0; i < 10; i++) printf("%d ", data[i]);
}

-1 -3 -2 -9 2 8 0 5 0 8

顺便说下,空间复杂度是O(1),不是O(l)。题目会不会做先不说,起码把题目什么意思得搞清楚。

实现方法跟快速排序一样,
int index=-1;
for(int i=0;i<length;i++)
{
if(array[i]<0)
{
++index;
swap(array[i],array[index]);
}
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!