80. 删除有序数组中的重复项 II

🟠   🔖  数组 双指针  🔗 力扣 LeetCode

题目

Given an integer array nums sorted in non-decreasing order , remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the firstk slots ofnums.

Do not allocate extra space for another array. You must do this by modifying the input arrayin-place with O(1) extra memory.

Example 1:

Input: nums = [1,1,1,2,2,3]

Output: 5, nums = [1,1,2,2,3,_]

Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,1,2,3,3]

Output: 7, nums = [0,0,1,1,2,3,3,,]

Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.

It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

题目大意

给定一个有序数组 nums，对数组中的元素进行去重，使得原数组中的每个元素最多暴露 2 个。最后返回去重以后数组的长度值。

解题思路

由于 nums 是有序数组，一般最容易想到使用双指针的解法，双指针的关键点：移动两个指针的条件。

• 快指针从头遍历数组，慢指针指向修改后的数组的末端；
• 当慢指针与快指针的数不相等时，移动慢指针到下一个位置，同时赋值慢指针；
• 当慢指针与快指针的数相等时，判断相等的次数，只有第一次相等时（因为不相等时已经移动过此数字一次了），才移动慢指针到下一个位置，同时赋值慢指针；
• 处理边界条件：当数组小于两个元素时，不做处理。

复杂度分析

• 时间复杂度：O(n)，其中n 表示 nums 的长度，需要遍历数组一遍。
• 空间复杂度：O(1)，用了常数个变量存储中间状态。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
	const len = nums.length;
	if (len < 3) return len;
	let slow = 0;
	let sameTime = 0;
	for (let i = 1; i < len; i++) {
		if (nums[slow] != nums[i]) {
			slow++;
			nums[slow] = nums[i];
			sameTime = 0;
		} else {
			sameTime++;
			if (sameTime === 1) {
				slow++;
				nums[slow] = nums[i];
			}
		}
	}
	return slow + 1;
};

相关题目

题号	标题	题解	标签	难度
26	删除有序数组中的重复项	[✓]	数组 双指针