[数据结构与算法] 【Leetcode数据结构算法题】原地移除元素（顺序表练习题）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【Leetcode数据结构算法题】原地移除元素（顺序表练习题） -> 正文阅读

[数据结构与算法]【Leetcode数据结构算法题】原地移除元素（顺序表练习题）

题目内容：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

在这里插入图片描述

leetcode题目链接（点击即可跳转）：

思路分析

①看完了题目，我们首先来理解一下题目的含义。
这个题目其实就算是说，有一个数组，而且还是一个整型数组，数组里面有一堆数字。然后给你一个特定的数字，这个数字有可能在数组里面找不到，也有可能找得到，如果能找到，就需要将数组里面中和这个数字相同的元素全部删除掉，最后得到一个新的数组。
题目里面说了“原地”，可能我们暂时并不理解“原地”是什么意思，我们可以先不管。为了解决上面说的“删除数组所有特定值”的这个问题，可以采取哪些方法呢？（先思考一下再进行往下看哦！）

是的，我们可以先创建一个临时数组，大小可以和原数组大小一样，然后将原数组中不为特定值的元素（也就是值 ≠ val）挪到临时数组中，跳过是特定值的元素（值 = val），最后将临时数组中的元素拷贝回原数组，即可解决这个问题。图解如下：
在这里插入图片描述
这种方法相信大部分同学都可以想到，但是这个方法有一个很明显的缺陷—当原数组很大的时候，比如说原数组有10万个数据，那么就需要开辟一个可以存10万个数据的临时数组。并且这个临时数组的大小还需要根据原数组的大小不停的变动，在实际中，这种方法很不实用（呆呆的，就是有点呆）。
那么能不能不需要创建临时数组就解决这个问题呢？
（额，既然我都问了，那肯定是有的）

方法一：元素覆盖法（有坑！）

我们可以借鉴顺序表的头删（或者中间任意位置删除）的操作—用后面的元素覆盖前面的元素实现数据的删除。
在这里插入图片描述
相关文章：
【数据结构学习笔记】二、线性表—顺序表篇（1）（画图详解+代码实现）

函数接口实现：

int removeElement(int* nums, int numsSize, int val){
    //首先判断数组是否为空
    if(numsSize == 0)
      return 0;
    int i = 0;//用来遍历数组元素
    int end = numsSize - 1;//用来记录最后一个元素的下标
    while(i <= end){
        //注意对最后一个元素的处理
        if(nums[i] == val){
            //从前往后依次覆盖
            for(int j = i;j < end; j++){
                nums[j]=nums[j+1];
            }
            //覆盖后数组长度-1
            end--;
        }
    }
    //此时新数组的长度是end+1
    return end+1;
}

当我们写完这段代码的时候，可能会欣喜若狂，实际上去测试的时候，却会嚎啕大哭，因为这段代码可能连测试案例都通过不了QAQ，Orz（跪了！）纳尼，怎么回事？？小朋友，是不是有很多问号？？？
在这里插入图片描述
测试案例通过不了的原因是“超出时间限制”，也就是耗时太多了，时间复杂度没有达到要求，假设问题规模为n（也就是原数组的长度为n），那么上面这段代码的时间复杂度为O(n^2)（n的平方的效率）。
时间复杂度、空间复杂度相关文章：
【数据结构学习笔记】一、数据结构介绍及算法分析（新手入门进阶指南）
然后我又悄悄回到 leetcode做题页面，重新审题，看有没有时间复杂度的限制要求，结果发现题目本身并没有对时间复杂度有任何要求，只要求了空间复杂度为O（1）（也就是原地起飞）。。。（坑爹啊！）

方法二：虚拟数组法（正确的方法）

既然元素覆盖的方法在 leetcode无法通过测试（虽然这种方法本身没有任何问题，自己在VS中写的测试用例也能通过），作为一名合格的编程学习者，自然要寻找另外一种更高效的方法。我们一开始谈到了临时数组法来处理这个问题，但是因为不满足空间复杂度O（1）的要求，所以没有采纳这种方法。但实际上这种方法的基本思想是正确的，将值非val的元素保留到数组中，值为val的元素丢弃掉。根据这种思想，我们可以想出虚拟数组的方式，也就是假设有一个临时数组，但是这个临时数组又不需要我们真正去开辟出来，而是借用原来的数组本身来实现临时数组的功能！（Nb，666，厉害了！！！）
算法图解：
在这里插入图片描述

函数接口实现：

int removeElement(int* nums, int numsSize, int val){
    //首先判断数组长度是否为0
    if(numsSize == 0)
       return 0;
    int src = 0;
    int dest = 0;
    while(src < numsSize){
        if(nums[src] != val){
            nums[dest++] = nums[src++];//保留给dest的同时，同时向后移动
        }
        else{
            src++;
        }
    }
    return dest;//此时数组的长度就是dest,dest是指向下个元素的下标
}