内存:2  时间:1

题目描述

若一个线性表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

提示

1、请使用C++编译并提交

2、只需提交删除区间内元素算法的部分

3、注意区间端点值是否合理(若不合理,返回false)

代码如下

#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;
}

代码来源于互联网,仅供参考!