（两种方法）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素

怼烎@ 2022-10-25 14:02 121阅读 0赞

为了方便描述过程，假定一个线性表结构体`ArrayList`

typedef struct ArrayList{
        
    	int data[N];  
    	int index;//初始值为-1，代表里面没有元素，使用时代表下标。
    }*List;

*  ### 第一种方法：顺序双指针法 ###

> 指针i控制向后遍历，指针j记录需要交换的位置。、
> 
> 1、进入循环，当遇到item元素时，不做任何处理，否则将指针i指向的值赋予指针j的位置，且指针j右移
> 
> 2、循环终止，最终将线性表的index等于j-1的位置。（最后一步的index位置，看index的含义，代表下标就j-1，逻辑位置就直接等于j即可）

![在这里插入图片描述][2021013123142442.gif_pic_center]

代码实现：

void deletes(List list,int item){
        
    	int j=0;
    	for(int i=0;i<=list->index;++i){
        
    		if(list->data[i]!=item){
        
    			list->data[j]=list->data[i];
    			++j;
    		}
    	}
    	list->index=j-1;
    }

*  ### 第二种方法：前后双指针法 ###

> 因为题目没有要求说非item元素是按照原来的顺序，所以可以采用该方法。
> 
> 1、设置前后两个指针，i=0，j=index
> 
> 2、i从前遍历，直到找到item元素的位置，j从后遍历，直到找到不是item元素的位置，将指针j指向的值放到指针i的位置，循环往复，直到i>j，结束循环。
> 
> 3、设置index的位置。

![在这里插入图片描述][20210131231528205.gif_pic_center]

代码实现：

void deletes(List list,int item){
        
    	int i=0,j=list->index;
    	while(i<=j){
        
    		while(i<=j && list->data[i]!=item) i++;
    		if(i<=j) while(i<=j && list->data[j]==item) j--;
    		if(i<=j) list->data[i++]=list->data[j--];
    	}
    	list->index = j;
    }

注意点：每次循环前都要先判断i，j的位置，防止出现越界，或不满足的情况。

[2021013123142442.gif_pic_center]: /images/20221024/f23eb442d0424e418d17af9a131a85a6.png
[20210131231528205.gif_pic_center]: /images/20221024/b760bd071cf14e27af876b914ab01e7e.png