【移除元素】问题

目录

一.题目描述

二.解题思路

三.代码

四.收获：【原地算法】

一.题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

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

二.解题思路

要解决 “原地移除数组中所有等于目标值val的元素，并返回剩余元素数量” 的问题，我们可以采用双指针法，该方法时间复杂度为 O (n)，空间复杂度为 O (1)，符合 “原地操作” 的要求。

核心思路

• 使用两个指针：慢指针（slow）和快指针（fast）。
• 快指针负责遍历整个数组，寻找不等于val的元素。
• 慢指针负责记录不等于val的元素应该放置的位置。
• 当快指针找到不等于val的元素时，将其赋值给慢指针指向的位置，然后慢指针向前移动一步。
• 遍历结束后，慢指针的位置即为剩余元素的数量k。

三.代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast<nums.length; fast++){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

四.收获：【原地算法】

通俗来讲，原地算法就是一种 “不另起炉灶” 的操作方式。

打个比方：
你有一个装着东西的盒子，现在想把里面的某些物品挑出来扔掉，只留下剩下的。

 

• 非原地算法：会再找一个新盒子，把要留下的东西一个个放进新盒子里，原来的盒子就不用了。
• 原地算法：不找新盒子，直接在原来的盒子里操作 —— 把要扔的东西拿走，剩下的东西往前挪一挪，挤一挤占满前面的位置，盒子本身还是原来那个，没换。

对应到编程里：
如果处理数组时，不创建新的数组，而是直接在原来的数组里修改、调整元素，最终结果就存在原数组的前半部分，这种做法就是原地算法。

 

比如上面的 “移除元素” 问题，用双指针在原数组里把有效元素往前挪，最后原数组的前 k 个元素就是结果，没有新数组，这就是典型的原地算法。

 

核心特点：省空间（不用额外开辟和原数组差不多大的空间），操作都在 “原地” 完成。

以上就是【移除元素】问题的全部解题过程，喜欢的话可以留个免费的关注呦~~