删除区间内的元素（线性表）
时间： 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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。