LeetCode27：移除元素

原题地址：. - 力扣（LeetCode）

题目描述

给你一个数组 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

实现思路

1. 首先检查数组是否为空，如果为空则直接返回0。
2. 使用一个指针 i 从数组的开始位置遍历数组。
3. 在每次迭代中，检查当前元素 nums[i] 是否等于 val。
4. 如果等于 val，则将 i 位置的元素替换为数组末尾的元素，并且减少数组的有效长度 n。
5. 如果不等于 val，则将 i 指针向前移动。
6. 重复这个过程直到 i 指针遍历完整个数组。
7. 返回数组的有效长度 n。

源码实现

class Solution {public int removeElement(int[] nums, int val) {// 如果数组为空，直接返回0if (null == nums) {return 0;}// 初始化指针i为0，表示从数组的开始位置遍历int i = 0;// 获取数组的长度int n = nums.length;// 使用while循环遍历数组while (i < n) {// 如果当前元素等于val，则将该元素与数组末尾的元素交换if (nums[i] == val) {nums[i] = nums[n - 1];// 减少数组的有效长度，但不增加i，因为i位置的元素已经改变n--;} else {// 如果当前元素不等于val，则将i指针向前移动i++;}}// 返回处理后的数组长度return n;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。这是因为每个元素最多被访问两次（一次是 i 指针的移动，如果遇到 val，则在交换时末尾的元素会被访问一次），所以总的比较和交换操作是线性的。

• 空间复杂度：O(1)，因为我们只使用了两个额外的变量 i 和 n，它们都是固定大小的，与输入数组的大小无关。因此，空间复杂度是常数级别的。