19、【顺序表】删除顺序表内所有指定元素（C++版）_对长度为n的顺序表l,编写一个时间复杂度为o(n),空间复杂度为o(1)的算法,//该

题目描述

对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

// 顺序表结构如下
typedef struct SeqList{
	ElemType* data;
	int length,MaxSize;
} SeqList;
1
2
3
4
5

题目分析

最终实现的结果是不存在目标元素的顺序表。
在这个过程中，若进行删除时，便需知道目标元素后的元素需移动的位数，在这个过程中需要知道两个量。一个是目标元素值，一个是目标元素个数。

解法1

从目标元素个数的相反条件来看，也就是知道非目标元素的个数。可以通过判断非目标元素，将其存储至顺序表中，即可直接得到最终结果。

使用k记录顺序表L中不等于x的元素个数，通过边扫描L边统计k，当不等于目标元素时就将该值存储至顺序表中，等于目标元素时就不存储该值，进行下一次判断。

void delTar_1(SeqList &L, ElemType e){
	int k = 0;
	for(int i = 0; i < L.length; i++){
		if(e != L.data[i]){
			L.data[k] = L.data[i];
			k++;
		}		
	}
	L.length = k;
}
1
2
3
4
5
6
7
8
9
10

时间复杂度为O(n)，空间复杂度为O(1)

解法2

用k记录顺序表L中等于x的元素个数，边扫描L边统计k，并将不等于x的元素迁移k个位置，最后修改L的长度。

void delTar_2(SeqList &L, ElemType e){
	int k = 0, i = 0;
	while(i < L.length){
		if(L.data[i] == e)
			k++;
		else
			L.data[i-k] = L.data[i];
		i++;
	}
	L.length = L.length-k;
}
1
2
3
4
5
6
7
8
9
10
11

时间复杂度为O(n)，空间复杂度为O(1)