leetcode【数组—简单】27. 删除元素

文章目录

• 前言
• 题目
• 题解
• No1提交：暴力解法
• No2提交：双指针方式(最优解)
• 参考资料

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

---

题目

题目来源leetcode

leetcode地址：27. 移除元素，难度：简单。

题目描述(摘自leetcode)：

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

本地调试代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        ...
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[]{3,2,2,3};
        int arrNums = solution.removeElement2(arr, 3);
        //打印输出
        for (int i=0;i<arrNums;i++) {
            if(i == 0){
                System.out.print("[");
            }
            System.out.print(arr[i]);
            if(i != arrNums-1){
                System.out.print(",");
            }else{
                System.out.print("]");
            }
        }
    }
}

---

题解

No1提交：暴力解法

思路：从左到右遍历整个数组，一旦某个元素等于目标值，那么后面的元素都统一向前面移动，并且对应检测长度-1，待检索位置-1(防止移动到指定覆盖索引位置的元素在下一次校验时校验)，其他见注释。

代码：时间复杂度：O(n^2)

public int removeElement(int[] nums, int val) {
    int currentLength = nums.length;  //初始值设置为数组长度，其会不断变化，实际可表示当前数组中不与val相同的元素数量
    for (int i = 0; i < currentLength; i++) {
        if(nums[i] == val){  
            for (int j = i+1; j < currentLength; j++) {  //整体数组向前移
                nums[j-1] = nums[j];
            }
            currentLength--; //由于向前移动，那么最后一个元素及倒数第二个元素重复，没有必要在之后重复进行检测
            i--;//由于整体向前移动，那么当前i位置上的元素被原本i位置后的元素覆盖，若是不-1，那么之后会i++，就会在下一次检测时漏掉一个
        }
    }
    return currentLength;
}

---

No2提交：双指针方式(最优解)

思路：使用一个指针left初始值设为0，同样从左到右遍历一遍数组，若是有不等于val的元素直接存储到数组left的索引下，接着left+1，一有不等于val的就继续重复操作，不断覆盖即可。

• 相较于之前暴力解法，效率大大提升，这里针对的就是!=val的情况，来对该情况进行统一处理。之前的则是针对于=val情况，整体后面的向前覆盖。

代码：时间复杂度O(n)

public int removeElement(int[] nums, int val) {
    int left = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] != val){  //一旦有!=val的值，依次存储到索引为left下标中，依次覆盖之前的值即可
            nums[left] = nums[i] ;
            left++;
        }
    }
    return left;
}

---

参考资料

[1]. 代码随想录leetcode刷题—移除元素题解：较详细思路

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.10.12