调整表中元素顺序(线性表)

调整表中元素顺序(线性表)

时间: 1ms        内存:2M

描述:

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

  

顺序表的定义为:

typedef struct
{
    ElemType data[SizeMax];
    int length;
} SqList;
  
需编写的算法为:
void move(SqList *&L);
  

注意:只需提交你所编写的算法即可

输入:

输入的数据有两行,第一行输入线性表的长度n,第二行依次输入n个元素。

输出:

输出的数据占一行,为调整之后的线性表,每个元素中间用空格分隔。

示例输入:

10
-12 25 -19 21 -18 -11 5 -18 9 -22

示例输出:

-12 -19 -18 -11 -18 -22 25 21 5 9

提示:

参考答案(内存最优[0]):

#include <iostream>

using namespace std;



struct SqList{
    int data[30];
    int length;
};


void move(SqList *&L){
    int temp;
    for(int i=0;i<L->length;i++){
        if(L->data[i]<0){
            for(int j=0;j<i;j++){
                if(L->data[j]>0){
                    temp=L->data[i];
                    L->data[i]=L->data[j];
                    L->data[j]=temp;
                    break;
                }
            }
        }
    }
}

int main()
{
    int num;
    struct SqList *sl=new SqList;
    cin>>num;
    sl->length=num;
    for(int i=0;i<num;i++){
        cin>>sl->data[i];
    }
    move(sl);
    for(int i=0;i<sl->length;i++){
        cout<<sl->data[i]<<" ";
    }
    cout<<endl;
    return 0;
}

参考答案(时间最优[0]):

#include <iostream>

using namespace std;



struct SqList{
    int data[30];
    int length;
};


void move(SqList *&L){
    int temp;
    for(int i=0;i<L->length;i++){
        if(L->data[i]<0){
            for(int j=0;j<i;j++){
                if(L->data[j]>0){
                    temp=L->data[i];
                    L->data[i]=L->data[j];
                    L->data[j]=temp;
                    break;
                }
            }
        }
    }
}

int main()
{
    int num;
    struct SqList *sl=new SqList;
    cin>>num;
    sl->length=num;
    for(int i=0;i<num;i++){
        cin>>sl->data[i];
    }
    move(sl);
    for(int i=0;i<sl->length;i++){
        cout<<sl->data[i]<<" ";
    }
    cout<<endl;
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注