跳至主要內容

27. 移除元素


27. 移除元素open in new window

🟢   🔖  数组 双指针  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an integer array nums and an integer val, remove all occurrences of val in nums in-placeopen in new window. 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 first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • 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删除有序数组中的重复项open in new window[✓]数组 双指针
203移除链表元素open in new window[✓]递归 链表
283移动零open in new window[✓]数组 双指针