Leetcode-移除元素

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目

链接：https://leetcode-cn.com/problems/remove-element/

方法1：开辟新空间

图解

方法：

• 遍历原来的数组，把不是要删除的元素放到新数组中，通过变量j控制新数组的下标
• 把新数组的元素拷贝回去nums中，j的数值就是删除元素后，数组的元素个数
• 释放动态开辟的新数组，并且把指针置空 ， 然后返回j的值

int removeElement(int* nums, int numsSize, int val)
{
   int* newarr = (int*)malloc(sizeof(int) * numsSize);
    if (newarr == NULL)
    {
        return 0;
    }
    memset(newarr, 0, sizeof(int) * numsSize);
    int i = 0;
    int j = 0;//标志新数组的下标
    for (i = 0; i < numsSize; i++)
    {
        //如果不是要删的元素就放到新数组
        if (nums[i] != val)
        {
            newarr[j++] = nums[i];
        }
    }
    //拷贝回去
    for (i = 0; i < j; i++)
    {
        nums[i] = newarr[i];
    }
    
    return j;
}

方法2：前后元素对比

思路：

• i指向前一个元素，j指向后一个元素，如果i指向的元素是要删除的，就把i后面的元素往前覆盖
• 注意：覆盖之后，i还要从原来删除的位置再次判断覆盖后的元素是否是要删除的元素，不可以直接i++ ，因为如果i和j指向的元素都是要删除的元素，覆盖之后，直接i++的话，就会出现错误， (如何再次再覆盖的位置判断： for循环中有i++，所以如果我们删除了一个元素，要让i–，和for循环的i++抵消，下一次进入循环就可以从该位置继续判断
• numsSize的数值也要改变，numsSize是数组中有效数字的个数，删除了一个元素，numsSize也要–

代码

int removeElement(int* nums, int numsSize, int val)
{
    int i = 0;
    int j = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] == val)
        {
            //把val后面的元素往前覆盖
            for (j = i + 1; j < numsSize; j++)
            {
                nums[j-1] = nums[j];
            }
            //删掉了一个元素
            numsSize--;
            i--;    //与for循环中的i++抵消 ,减一后再加一，再次比较被删除元素的下标现在所对应的前后元素  
        }
    }
    return numsSize;
}

方法3：双指针

方法：

• 使用两个变量，分别从起始位置开始
• 如果i指向的元素不是要删除的元素，就放到j下标位置处，i++，j++
• 如果i指向的元素是要删除的元素，那就i++，j保存不动
• 最后j的数值就是数组删除元素之后剩余的元素个数

图解

方法：

 int removeElement(int* nums, int numsSize, int val)
 {
    int i = 0;
    int j = 0;
    while(i<numsSize)
   {
        if(nums[i] !=val)
        {
          nums[j++] = nums[i++];
        }
        else
        {
            i++;
        }
   }
    return j;
}

\