630 字
3 分钟
80. 删除有序数组中的重复项 II
80. 删除有序数组中的重复项 II
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 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] <= 104nums 已按升序排列思路
暴力统计
- 使用一个哈希表统计每个元素出现的次数。
- 遍历数组，将出现次数不超过2次的元素移动到结果数组中。
- 最后返回结果数组的长度。
双指针
- 由于数组是有序的，且每个元素最多出现两次。因此再遍历时，只需要判断当前元素是否与前两个元素相同即可。
- 使用双指针法，
left指向结果数组的末尾，i指向当前遍历的元素。 - 当
i指向的元素与left - 2指向的元素不同时，将i指向的元素赋值给left，并将left向后移动一位。 - 注意：当
nums.size() = 1时，left会超过范围，因此需要返回min(left, n)。
额外空间暴力完成
class Solution {public: int removeDuplicates(vector<int>& nums) { unordered_map<int, int> count; int left = 0; for(int i = 0; i < nums.size(); i++){ // 统计nums[i]出现次数 count[nums[i]]++; // 如果没超过2次 if(count[nums[i]] <= 2){ // 移动元素，更新位置 nums[left] = nums[i]; left++; } // 如果超过2次，忽略掉 } return left;
}};双指针法
class Solution {public: int removeDuplicates(vector<int>& nums) { int left = 2; int n = nums.size(); // 由于原数组是有序排序的，且单个元素不超过2个 // 所以只需要和前2个元素比较即可判断是否大于2个。 for(int i = 2; i < n; i++){ if(nums[i] != nums[left - 2]){ nums[left] = nums[i]; left++; } } // 如果nums.size() = 1, left超过范围 return min(left, n);
}}; 80. 删除有序数组中的重复项 II
https://chrisnake11.github.io/blog/posts/coding/leecode/80-删除有序数组中的重复项-ii/