顺序表oj之删除特定的元素

一 题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二 解答

思路

由于涉及到原地删除，因此需要考虑双指针了。

使用双指针：可以在一个数组中通过两个指针指向的变量来控制，实现原地覆盖删除。

定义两个指针，分别都指向开头。fast用来判断值是否等于val，slow用来标识需要覆盖的位置以及表达最后的返回值。

如果val的值不等于val，那么就是需要保留的数字，因此需要把他放到数组中去，即slow标识的位置。放下去之后，slow指向下一个位置，准备下一次得接受，fast继续向后遍历，寻找要删除的数据。

如果fast找到了val，那么这个值是需要被删除的，因此不能放在slow的位置，跳过他，fast继续寻找下一个位置的数据。

直至遍历完所有的数据。

图解思路：

 

代码实现：

int removeElement(int* nums, int numsSize, int val){
int slow=0;
int fast=0;

while(fast<numsSize)
{
    if(nums[fast]!=val)
    {
        nums[slow++]=nums[fast++];
    }
    else
    {
        fast++;
    }
}

return slow;
}

需要注意的是，由于遍历完之后，slow标识的位置就是整个数组的长度了。在最后一个元素的下一个位置。