Leetcode 27：Remove Element

2024-01-26 19:09:58

Leetcode 27：Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

说人话：

给定一个数组 nums 和一个数值 val，将数组中所有等于 val 的元素删除，并返回剩余元素的个数。

几个要点：

原地移除
返回的是长度，而不是数组
空间复杂度为 O(1)
元素顺序可以打乱，不需要考虑数组中超出新长度后面的元素

示例1：

示例：

[法1] 暴力法

虽然题目规定了空间复杂度必须为 O(1)，也就是不允许我们使用辅助空间，但是我们如果没有思路的话，也可以先使用暴力法把问题解决了之后，再来考虑它的优化策略。因为这里我们暴力法的缺点就是需要用到 O(n) 的辅助空间，我们在优化的时候紧紧抓住这个点就可以了。

思路

① 遍历一遍数组，把非 val 的元素依次放到一个临时数组中；

② 复制临时数组到原数组

代码

class Solution {
    public int removeElement(int[] nums, int val) {

      	//临时数组
        int[] tempNums = new int[nums.length];
				//临时数组索引，记录非val元素的个数
        int j = 0;
				//遍历原数组
        for (int i = 0; i < nums.length; i++) {
						//将非val元素放入临时数组中
            if (nums[i] != val){
                tempNums[j] = nums[i];
                j++;
            }
        }
				//复制数组
        for (int i = 0; i < nums.length; i++) {
            nums[i] = tempNums[i];
        }
        return j;
    }
}

代码分析

时间复杂度：两个并行的 for 循环，时间时间复杂度是 O(n)
空间复杂度：因为用到了一个临时数组 tempNums，所以空间复杂度去 O(n)

改进思路

很显然我们上面的暴力法虽然将问题解决了，但是不满足题目要求的空间复杂度O(1)。我们改进的思路就想办法不借助新数组，直接在原数组上进行操作。

其实这道题非常像Leetcode 283：Move Zeroes，我们可以从中获取一些思路：

思路① 遍历 nums，在遇到非 val 元素的时候，直接把它赋值到前面就可以了。而且由于非 val 元素的个数一定是小于或等于整个数组的元素个数的，所以在赋值到前面的时候，我们不用担心这个赋值会覆盖掉任何的数据。

思路② 遍历 nums，将前面的 val 元素与后面的非 val 元素进行交换。

[法2] 不使用辅助空间

思路

① 建立两个索引i和j，i 负责遍历数组，j负责保证[0…j) 都是非 val 元素

② 遍历数组 nums，一旦遇到非 val 元素，就覆盖前面的 val 元素（nums[j]）

代码

class Solution {
    public int removeElement(int[] nums, int val) {

        //[0...j)都是非val元素
        int j = 0;

        //遍历数组
        for(int i=0;i<nums.length;i++){
            //找到非 val 元素
            if(nums[i]!=val){
                //用非 val 元素覆盖前面的 val 元素
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

提交结果

代码分析

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

改进思路

本算法已经能够满足题目的要求了。不过如果我们要更加严格一点的话，还可以再改进。改进的地方就是本算法会导致 nums 中的元素发生改变，因为我们是把 val 元素给覆盖掉了，所以执行完算法后，nums 会从原来有 val 元素变为没有 val 元素。

要改进的话，那我们就可以用交换来替代覆盖。

[法3] 交换

思路

① 建立 2 个索引，一个是非val元素索引j，一个是数组遍历索引 i

② 遍历到数组第 i 个元素后，保证 [0…i] 中所有非val元素都按顺序排列在 [0…j) 当中，同时要保证 [j…i] 为val

代码

class Solution {
    public int removeElement(int[] nums, int val) {

        //[0...j)都是非val元素
        int j = 0;

        //遍历数组
        //[j...i]都是 val 元素
        for(int i=0;i<nums.length;i++){
            //找到非 val 元素
            if(nums[i]!=val){
                //将非val元素和前面的val元素（nums[j]）进行交换
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j++;
            }
        }
        return j;

    }
}

提交结果

代码分析

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

改进思路

按照前面的思路的话，容易出现自身交换的不必要行为。设想一下 nums 中所有元素都不是 val，那每次 nums[i] 都等于 nums[j] ，但是还要进行 swap(nums[i],nums[j])，就造成了浪费。

[法4] 避免自身交换

思路

加入判断，当 i ≠ j 的时候，才对 nums[i] 和 nums[j] 进行交换操作，避免自身交换

代码

class Solution {
    public int removeElement(int[] nums, int val) {

        //[0...j)都是非val元素
        int j = 0;

        //遍历数组
        //[j...i]都是 val 元素
        for(int i=0;i<nums.length;i++){
            //找到非 val 元素
            if(nums[i]!=val){
                //避免自身交换
                if(i != j){
                    //将非val元素和前面的val元素（nums[j]）进行交换
                    int temp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = temp;
                }

                j++;
            }
        }
        return j;

    }
}

提交结果

代码分析

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

码农公寓