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

阿伟@t

发布于 2023-10-10 15:09:23

1120

发布于 2023-10-10 15:09:23

文章被收录于专栏：cs阿伟cs阿伟

前言：

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

移除元素

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

题目要求：

题目分析：

思路1：

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

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

思路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
}