卷进大厂系列之LeetCode刷题笔记：移除元素（简单）

1年前 (2023) 程序员胖胖胖虎阿

122 0 0

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以引用方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

	// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

	// 在函数里修改输入数组对于调用者是可见的。	
for (int i = 0; i < len; i++) {
    print(nums[i]);// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：


输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

涉及算法

这道题目属于简单题型，涉及到数据结构中的数组。对于数组我们要知道以下内容：

数组是存储在连续内存空间的相同类型数据的集合
数组下标都是从0开始
数组在内存空间的地址都是连续的

那么根据题目，我们可以提炼的关键点：

不要使用额外的数组空间，即使用 O(1) 额外空间

根据这个关键点，直接就排除了我们使用额外数组的想法。但这个题目来说，还是不难的，只要根据数组的性质（数组再内存的地址是连续的），不直接去通过查找到对应的元素直接删除就是可以的，换句话说，就是在找到对应数值等于 val 的元素后，我们不是简单删除，而是通过覆盖的方式来解决。

覆盖指的是数组中元素的移动，例如当前元素的位置被其后面元素通过向前移动一位占用了

上面都搞清楚了，就可以开始写了，不懂的可以留言讨论！

题目解答

Java题解一

对于这个题目的解答，很容易想到的就是暴力解法（双循环），直接就两个for循环：第一个for循环用来遍历数组元素，查找数值等于 val 的元素；第二个for循环用来实现数组的中元素的移动，覆盖满足条件的元素。

class Solution {
    public int removeElement(int[] nums, int val) {
        //暴力解法，双循环
        int size = nums.length;
        for(int i =0; i < size; i++){ //遍历数组，查找相同元素
            if(val == nums[i]){ //找到需要移除得元素后，该元素后面的整体从后向前移动一位
                for(int j = i + 1; j < size; j++ ){ //再来一个循环，数组的中元素的移动，覆盖满足条件的元素
                    nums[j-1] = nums[j];  //不是能nums[j] = nums[j +1]; j+1 就不小于size了数组越界了
                }
                i--; //数组元素都向前移动了一位，i也向前移动一位
                size--; //数组长度减1
            }
        }
        return size; //返回最后结果
    }
}

卷进大厂系列之LeetCode刷题笔记：移除元素（简单）
复杂度分析

时间复杂度： O(n²)
空间复杂度： O(1)

Java题解二

从上面我们也可以看出来，通过双循环的暴力解法的时间复杂度是 O(n²)，还是很耗时间的（暴力解法也是解法，不过各位不应局限于此）。那改进暴力解法的关键点就是能否把双循环这个耗时的操作进行改进。
需要注意的是，针对删除操作，我们得有两个操作：一个查找和一个覆盖。如果能够在一次for循环里面实现这两个操作，那就是节省了一个for循环，时间复杂度就会降低一个级别。对于这种一趟循环，两个操作的问题，双指针法（快慢指针）是很好的解决办法。在双指针解法中：第一个指针（快指针）用来实现查找操作；第二个指针（慢指针）和第一个指针（快指针）一起实现用来实现覆盖操作。

class Solution {
    public int removeElement(int[] nums, int val) {
        //双指针（快慢指针）
       int slowIndex = 0; //定义慢指针，开始指向起始位置
       int fastIndex = 0;//定义快指针，开始指向起始位置
       for(; fastIndex < nums.length; fastIndex ++){ //for循环，遍历数组，查找相同元素
           if(nums[fastIndex] != val){ //如果不是要找的元素（如果是，快指针不进if，接着后移）
               nums[slowIndex] = nums[fastIndex]; //将快指针的值赋给慢指针
               slowIndex++; //慢指针向后移动一位
                
           }
       }
       return slowIndex; //慢指针就是实现了覆盖后的结果数组
    }
}