[leetcode刷题]面试经典150题之4删除有序数组中的重复项II（中等）

思路大致跟上一题一样

题目

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

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

解决思路：

1. 双指针法：可以使用两个指针，一个用于遍历数组，另一个用于跟踪新数组中允许的唯一元素的位置。
2. 保持最多两次重复：由于数组是有序的，我们只需要关注每个元素的出现次数是否大于 2 次。因此，对于每个元素，允许其最多出现两次。

具体步骤：

1. 使用两个指针 i 和 j。

   • i：是慢指针，表示当前数组中有效元素的最后一个位置。
   • j：是快指针，用于遍历数组。

2. 初始化 i = 1，表示前两个元素无论如何都需要保留，因为我们允许元素最多出现两次。

3. 从第三个元素（j = 2）开始遍历数组：

   • 如果当前元素 nums[j] 不等于 nums[i-1]，说明它与前两个元素不同或者第一次遇到这个元素，我们可以将其放到 nums[i+1] 位置。
   • 如果相等，则跳过这个元素。

4. 遍历结束后，i+1 就是最终数组的长度。

代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 2:  # 如果数组长度小于等于2，直接返回长度
            return len(nums)
        
        i = 1  # 慢指针，指向有效数组的末尾
        for j in range(2, len(nums)):  # 快指针，从第三个元素开始遍历
            if nums[j] != nums[i-1]:  # 如果当前元素与nums[i-1]不同
                i += 1  # 移动慢指针
                nums[i] = nums[j]  # 更新有效数组
        
        return i + 1  # 返回数组长度

原文地址：https://blog.csdn.net/m0_63680328/article/details/142406629

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！