当前位置：首页 > article >正文

LeetCode：27. 移除元素

article 2024/12/23 1:28:56

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

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

算法专栏： 👉🏻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.双指针搜索

就是使用两个指针，一个指针（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;
}