力扣27.移除元素【顺序表】

2022-12-02 89

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 力扣27.移除元素【顺序表】

🎈今日心语：你所看到的惊艳，都曾被平庸所历练。

前言：

在解题过程中一定要画图进行思考，然后再敲代码。

文章目录

移除元素

结语：

移除元素

初学数据结构顺序表，要求时间复杂度为O(N)，空间复杂度为O(1)：力扣oj链接

题目要求：

题目分析：

思路1：

查找一个删除一个，与顺序表中查找的思路一样。

时间复杂度:O(N²)，最坏的情况是数据基本都与val相等，删除一个的时间复杂度为O(N)，删除N个为O(N²)。

思路2：

提供一个临时数组tmp，以空间换时间，不进行挪动。

当，src指向0时，0 != val , 此时将src指向的值赋值到dst指向的位置，src和dst都向后挪动以为，开始寻找下一个。若src指向的值等于val，则dst位置不变，src向后挪动。

最后用tmp中的值从起始位置覆盖原来的数据，释放tmp并改动size的位置以删除后面的元素。

思路3：

再优化，不创临时数组，直接在原始数据上进行操作，使用双指针。

时间复杂度O(N)

空间复杂度O(1)

开始时src和dst都指向初始位置，src负责和val进行比较，当src指向的值不等于val时，将这个值放到dst指向的位置，然后src和dst一起向后挪动。

当src指向的值=val时，dst不动，src向后偏移。

最终代码：

int removeElement(int* nums, int numsSize, int val)
{
int dst = 0,src = 0;
while(src<numsSize)//结束标志src>=numsize
{
     if(nums[src] == val)
     {
         src++;
     }
     else
     {
         nums[dst] = nums[src];
         src++;
         dst++;
     }
}
    return dst;//dst刚好是最后一个元素下一个位置，下标=size
}

为了减少代码量，也可以采取以下两种写法：

int removeElement(int* nums, int numsSize, int val)
{
int dst = 0,src = 0;
while(src<numsSize)//结束标志src>=numsize
{
     if(nums[src] == val)
     {
         src++;
     }
     else
     {
         nums[dst++] = nums[src++];
     }
}
    return dst;//dst刚好是最后一个元素下一个位置，下标=size
}

int removeElement(int* nums, int numsSize, int val)
{
int dst = 0,src = 0;
while(src < numsSize)//结束标志src>=numsize
{
     if(nums[src] != val)
         nums[dst++] = nums[src];
    src++;
}
    return dst;//dst刚好是最后一个元素下一个位置，下标=size
}

结语：

走到这里本题就介绍完了，希望以上内容对大家有所帮助👀，如有不足望指出🙏

前路漫漫！努力变强💪💪 吧！！