LeetCode 0080.删除有序数组中的重复项 II：双指针 - C++/Java5 行版

【LetMeFly】80.删除有序数组中的重复项 II：双指针 - C++/Java5 行版

力扣题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

 

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

 

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

解题方法一：快慢指针

使用一个慢指针指向数组中已经合法的元素（初始值为1，因为前两个元素必合法），使用一个快指针指向当前遍历到的元素。

快指针从下标2开始遍历，如果快指针指向元素和慢指针指向元素的前一个元素不同，则快指针指向元素可以合法地加入数组（慢指针右移一位，快指针元素放到慢指针位置）。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-02-09 08:44:41* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-09 08:48:30*/
class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1;for (int fast = 2; fast < nums.size(); fast++) {if (nums[fast] != nums[slow - 1]) {nums[++slow] = nums[fast];}}return min((int)nums.size(), slow + 1);}
};

Python

'''
Author: LetMeFly
Date: 2025-02-09 08:53:38
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-09 08:55:23
'''
from typing import Listclass Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = 1for fast in range(2, len(nums)):if nums[fast] != nums[slow - 1]:slow += 1nums[slow] = nums[fast]return min(len(nums), slow + 1)

Java

/** @Author: LetMeFly* @Date: 2025-02-09 08:53:42* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-09 08:58:07*/
class Solution {public int removeDuplicates(int[] nums) {int slow = 1;for (int fast = 2; fast < nums.length; fast++) {if (nums[fast] != nums[slow - 1]) {nums[++slow] = nums[fast];}}return Math.min(slow + 1, nums.length);}
}

Go

/** @Author: LetMeFly* @Date: 2025-02-09 08:53:44* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-09 09:00:09*/
package mainfunc removeDuplicates(nums []int) int {slow := 1for fast := 2; fast < len(nums); fast++ {if nums[fast] != nums[slow - 1] {slow++nums[slow] = nums[fast]}}return min(slow + 1, len(nums))
}

解题方法二：易想版本

来自2022.6.19，当时就想写题解了。

如果方法一难想怎么办？很简单，使用两个指针指向“相同连续元素”的始末位置总可以了吧。

每次得到一种元素的始末位置后，就放置min(2, 这种元素个数)个这种元素到“合法数组”中就好了。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2022-06-19 09:51:38* @LastEditors: LetMeFly* @LastEditTime: 2022-06-19 10:31:22*/class Solution {
public:int removeDuplicates(vector<int>& nums) {int cnt = 0;int l = 0, r = 1;  // [l, r)相同nums.push_back(1e5);for (; r < nums.size(); r++) {if (nums[r] != nums[l]) {for (int i = 0; i < min(2, r - l); i++) {nums[cnt++] = nums[r - 1];}l = r;}}return cnt;}
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

Tisfy：https://blog.letmefly.xyz/2025/02/09/LeetCode 0080.删除有序数组中的重复项II