首页 > 代码库 > 【转载】顺序表中删除为x的所有元素,时间空间复杂度有要求
【转载】顺序表中删除为x的所有元素,时间空间复杂度有要求
解法一:
首先确定顺序表L中的第一个值为x的元素位置i,然后依次检查L.data[i+1]~L.data[L.length-1]中每个元素L.data[j](i+1<=j<L.length),若L.data[j]!=x,则将L.data[j]存入L.data[i]中,并令i增1。最后顺序表长度为i。算法如下:
void delall(Sqlist *l,int x){ int i=0,j; while(i<l->length && l->data[i]!=x) i++; for(j=i+1;j<l->length;j++) if(l->data[j]!=x) { l->data[i++]=l->data[j]; } l->length=i;}本算法只扫描一次顺序表,即将值为x的元素前移一次,其时间复杂度为O(n)
解法二:
从头开始扫描顺序表L,用k记录下元素值等于x的元素个数,对于不等于x的元素,前移k个位置,这种算法复杂度为O(n),其中n为顺序表的长度,算法如下:
void delall(Sqlist *l,int x){ int i=0,j=0; while(i<l->length) { if(l->data[i]==x) j++;//j记录被删记录的个数 else l->data[i-j]=l->data[i];//前移j个位置 i++; } l->length-=j;}
【转载】顺序表中删除为x的所有元素,时间空间复杂度有要求
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。