顺序表删除值为x的元素，时间复杂度为O(n)

傷城~ 2021-12-17 03:13 249阅读 0赞

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

解决思想：

这个问题一个复杂的解决方法是依次遍历顺序表，遇到值为x的元素就删除，直到顺序表遍历完。这种解决方法的时间复杂度为O(n\*n)，不满足题意。以下有两种解决方案：

(1)用count记录顺序表中值**不等于**x的元素个数，边遍历顺序表L边记录count的个数，遍历时当元素当前位置的值不等于x时，向前移动到count的位置，遍历完成后修改顺序表L的长度。

(2)用count记录顺序表中值**等于**x的元素个数，边遍历顺序表L边记录count的个数，遍历时当元素当前位置的值不等于x时，向前移动count个位置，遍历完成后修改顺序表L的长度。

代码：

(1)

void sqlistDelete_x1(Sqlist &L, ElemType x){
    	int count=0;                 //用来记录顺序表中不等于x的元素个数
    	for (int i = 0; i < L.length; i++){
    		if (L.data[i] != x){
    			L.data[count] = L.data[i];
    			count++;
    		}
    	}
    	L.length = count;
    }

(2)

void sqlistDelete_x2(Sqlist &L, ElemType x){
    	int count = 0;              //用来记录顺序表中等于x的元素个数
    	for (int i = 0; i < L.length; i++){
    		if (L.data[i] == x){
    			count++;
    		}
    		else
    		{
    			L.data[i - count] = L.data[i];
    		}
    	}
    	L.length -= count;
    }

完整代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    #define Maxsize 40
    typedef int ElemType;
    typedef struct Sqlist{
    	ElemType data[Maxsize];
    	int length;
    };
    void sqlistDelete_x1(Sqlist &L, ElemType x){
    	int count=0;                 //用来记录顺序表中不等于x的元素个数
    	for (int i = 0; i < L.length; i++){
    		if (L.data[i] != x){
    			L.data[count] = L.data[i];
    			count++;
    		}
    	}
    	L.length = count;
    }
    void sqlistDelete_x2(Sqlist &L, ElemType x){
    	int count = 0;              //用来记录顺序表中等于x的元素个数
    	for (int i = 0; i < L.length; i++){
    		if (L.data[i] == x){
    			count++;
    		}
    		else
    		{
    			L.data[i - count] = L.data[i];
    		}
    	}
    	L.length -= count;
    }
    int main(){
    	Sqlist L;
    	ElemType x;
    	printf_s("输入顺序表L的长度：");
    	scanf_s("%d", &L.length);  //建立顺序表L
    	printf_s("\n输入顺序表中各个元素的数值：");
    	for (int i = 0; i < L.length; i++){
    		cin >> L.data[i];
    	}
    	printf_s("输入要删除元素x的值：");
    	cin >> x;
    	//sqlistDelete_x1(L, x);
    	//printf_s("\n方法1删除后的结果：");
    	//for (int i = 0; i < L.length; i++){
    	//	cout << L.data[i] << "\t";
    	//}
    
    	//sqlistDelete_x2(L, x);
    	//printf_s("\n方法2删除后的结果：");
    	//for (int i = 0; i < L.length; i++){
    	//	cout << L.data[i] << "\t";
    	//}
    	system("pause");
    	return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

![20190707001440663.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20211214/53e2b729e1c44d1f80597dc14c56e46b.png
[20190707001440663.png]: /images/20211214/f01f160fecc74e0f9ba7063b0356609c.png