27. 移除元素
题目描述
输入整数数组 nums 和一个值 val。设 nums 中不等于 val 的元素共有 k 个。
直接在 nums 上修改，不要开新数组：把这 k 个元素放到 nums 的前 k 个位置，它们之间的顺序可以改变。后面的位置放什么都不影响判题。
函数返回 k。判题时会先核对 k，再把 nums 前 k 个元素排序后与标准答案比较。
本页示例输出写成 [k, nums 的前 k 个元素] 的形式。
输入：nums = [3,2,2,3], val = 3 输出：[2,[2,2]]
解释：去掉两个 3 后剩下两个 2，返回 2。
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：[5,[0,1,3,0,4]]
解释：去掉三个 2 后剩下 0,1,3,0,4 五个数，返回 5；这五个数的顺序不影响判题。
数据范围
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
解题思路：快慢双指针
用快慢指针。快指针从左到右读每个数 x；慢指针 k 是下一个要写入的位置。x 不等于 val 就把它写到 nums[k]，k 加 1；x 等于 val 就跳过。因为 k 不会超过读取位置，写入只会覆盖已经读过的数。
为什么正确
nums[:k] 恰好是已读部分中所有不等于 val 的数，并保持原顺序。
复杂度分析
时间 O(n)，每个数读一次、最多写一次；空间 O(1)。
易错点
不要在遍历时用 pop/remove 删除元素：下标会错位，而且每次删除是 O(n)，整体退化为 O(n²)。返回的是个数 k，不是数组。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k = 0
for x in nums:
if x != val:
nums[k] = x
k += 1
return kclass Solution {
public int removeElement(int[] nums, int val) {
int k = 0;
for (int x : nums) {
if (x != val) {
nums[k] = x;
k++;
}
}
return k;
}
}class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for (int x : nums) {
if (x != val) {
nums[k] = x;
k++;
}
}
return k;
}
};func removeElement(nums []int, val int) int {
k := 0
for _, x := range nums {
if x != val {
nums[k] = x
k++
}
}
return k
}var removeElement = function(nums, val) {
let k = 0;
for (const x of nums) {
if (x !== val) {
nums[k] = x;
k++;
}
}
return k;
};function removeElement(nums: number[], val: number): number {
let k = 0;
for (const x of nums) {
if (x !== val) {
nums[k] = x;
k++;
}
}
return k;
}其他解法
两种方法都是 O(n) 时间、O(1) 空间；快慢指针保持原顺序，首尾指针不保序但在待删元素少时赋值更少。
解法 2：首尾双指针 时间 O(n)，空间 O(1)
left 从头、right 从尾部之后出发，[left, right) 是待检查区间。nums[left] 等于 val 时，用区间最后一个元素 nums[right-1] 覆盖它，并让 right 减 1，left 不动，因为换来的元素还没检查。否则 left 加 1。两指针相遇时 left 就是保留元素的个数。
每个元素最多被访问一次，要删的元素很少时赋值次数远少于快慢指针。代价是会打乱保留元素的相对顺序，本题允许这样做。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left, right = 0, len(nums)
while left < right:
if nums[left] == val:
nums[left] = nums[right - 1]
right -= 1
else:
left += 1
return leftclass Solution {
public int removeElement(int[] nums, int val) {
int left = 0, right = nums.length;
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
}class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};func removeElement(nums []int, val int) int {
left, right := 0, len(nums)
for left < right {
if nums[left] == val {
nums[left] = nums[right-1]
right--
} else {
left++
}
}
return left
}var removeElement = function(nums, val) {
let left = 0, right = nums.length;
while (left < right) {
if (nums[left] === val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
};function removeElement(nums: number[], val: number): number {
let left = 0, right = nums.length;
while (left < right) {
if (nums[left] === val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}