27. 移除元素
27. 移除元素
题目
Given an integer array nums
and an integer val
, remove all occurrences of val
in nums
in-place. The order of the elements may be changed. Then return the number of elements innums
which are not equal toval
.
Consider the number of elements in nums
which are not equal to val
be k
, to get accepted, you need to do the following things:
- Change the array
nums
such that the firstk
elements ofnums
contain the elements which are not equal toval
. The remaining elements ofnums
are not important as well as the size ofnums
. - Return
k
.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
题目大意
给定一个数组 nums 和一个数值 val
,将数组中所有等于 val
的元素删除,并返回剩余的元素个数。
解题思路
这道题和 第 283 题 基本一致,283 题是删除 0,这一题是给定的一个 val,实质是一样的。
可以使用快慢指针,fast
指针往前遍历数组,遇到与 val
不同的数,就将它往前移,用 slow
指针标记与 val
不同的数要移动的位置,最后返回 slow
即可。
复杂度分析
- 时间复杂度:
O(n)
,其中n
表示nums
的长度,需要遍历数组一遍。 - 空间复杂度:
O(1)
,用了常数个变量存储中间状态。
代码
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function (nums, val) {
const len = nums.length;
let slow = 0;
for (let fast = 0; fast < len; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
26 | 删除有序数组中的重复项 | [✓] | 数组 双指针 | |
203 | 移除链表元素 | [✓] | 递归 链表 | |
283 | 移动零 | [✓] | 数组 双指针 |