LeetCode：27. 移除元素

2023-04-23 45

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

一、🌱27. 移除元素

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
难度：简单
提示：

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

说明：

输入：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]，也会被视作正确答案。

🌴解题

1.暴力查找移除

就是套两层for循环，一层遍历数组，一层移动数组元素。
这种方法实现简单，无技术性，时间复杂度达到O(n^2^)。

2.双指针搜索

就是使用两个指针，一个指针（for循环里的i）从==数组首==开始找等于val的元素，另一个指针（end）从==数组尾部==开始找不等于val的元素，当i找到一个元素等于val，就和end指向元素交换，并且记录下等于val元素的个数，用于之后返回有多少个剩余数组。

例如：

int[]nums = {4,2,0,2,2,1,4,4,1,4,3,2};
int val = 4;

code

public static int removeElement(int[] nums, int val) {
//题目存在0个元素数，为了方便就这样写了
    if(nums.length==0)
        return 0;
    if(nums.length==1){
        if(nums[0]==val)
            return 0;
        else
            return 1;
    }

    int allv=0;
    int end= nums.length-1;
    for (int i = 0; i <= end; i++) {
        if(nums[i]==val){
            allv++;
            while(nums[end]==val){
                if(end==i)
                    break;
                end-=1;
                allv++;
            }
            nums[i]=nums[end];
            nums[end]=0;
            end-=1;
        }
    }

    return nums.length-allv;
}