删除区间内的元素(线性表)

删除区间内的元素(线性表)

时间: 1ms        内存:2M

描述:

若一个线性表L采用顺序存储结构,其中元素都为整数。设计一个算法,删除元素值在[x,y]之间的所有元素,要求算法的时间复杂度为O(n),空间复杂度为O(1). 

顺序表定义为:

typedef struct
{
    ElemType data[SizeMax];
    int length;
} SqList;

需编写的算法为:

bool Delete(SqList *&L,ElemType x,ElemType y);

注意:只需提交删除区间内元素的算法Delete部分。

输入:

输入的第一行代表线性表的长度n,n<=SizeMax。第二行输入n个元素并插入到线性表中,第三行输入两个整数x,y,确定区间。

输出:

输出的数据占两行,第一行是删除之后线性表的长度length,接下来的一行是线性表中的每个元素。

示例输入:

10
5 3 6 2 1 9 8 7 4 0
3 7

示例输出:

5
2 1 9 8 0

提示:

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

#include <iostream>

#define SizeMax 30

using namespace std;

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

bool Delete(SqList *&L,int x,int y){
    /*if(x<-2147483648||y>2147483647){
        return false;
    }*/
    int i=0;
	while(i<L->length){
        if(L->data[i]>=x&&L->data[i]<=y){
            for(int j=i;j<L->length;j++){
                L->data[j]=L->data[j+1];
            }
            L->length--;
        }else{
            i++;
        }
	}
	return true;
}

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

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


#include <stdio.h>
#include <stdlib.h>
#define SizeMax 10000
typedef int ElemType;
typedef struct
{
    ElemType data[SizeMax];
    int length;
} SqList;
void CreateList(SqList *&L,ElemType n)
{
    if(n>SizeMax)return;
    L=(SqList*)malloc(sizeof(SqList));
    for(int i=0; i<n; i++)
        scanf("%d",&L->data[i]);
    L->length=n;
}bool Delete(SqList *&L,int x,int y)
{
    if(x>y)return false;
    int n=L->length;
    for(int i=0,j=0;i<n;i++)
    {
        if(L->data[i]>=x&&L->data[i]<=y)L->length--;
        else L->data[j++]=L->data[i];
    }
    return true;
}
void Print(SqList *L)
{
    int i;
    printf("%d\n",L->length);
    for(i=0; i<L->length; i++)
        printf(i!=L->length-1?"%d ":"%d\n",L->data[i]);
}
void DestroyList(SqList *&L)
{
    free(L);
}
int main()
{
    SqList *L;
    ElemType n,x,y;
    scanf("%d",&n);
    CreateList(L,n);
    scanf("%d%d",&x,&y);
    if(Delete(L,x,y))
        Print(L);
    DestroyList(L);
    return 0;
}

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

点赞

发表评论

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