删除有序数组中的重复项I
给你一个 非严格递增排列 的数组 nums
,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums
中唯一元素的个数。
思路:双指针(不要被名字吓到,其实就是两个ij变量)
class Solution:def removeDuplicates(self, nums: List[int]) -> int:if len(nums) == 0:return 0i = 0for j in range(1, len(nums)):if nums[j] != nums[i]:i += 1nums[i] = nums[j]return i + 1
定义两个指针 i
和 j
,其中 i
是慢指针,而 j
是快指针。当 nums[i] == nums[j]
时,递增 j
以跳过重复项;当 nums[i] != nums[j]
时,将 nums[j]
的值复制到 nums[i+1]
处,并递增 i
。最后返回 i+1
即为去重后数组的新长度。
最后应该只会检查前i+1个元素是否符合,如果系统不是这样检测,可以更改一下nums截取
即
nums[:] = nums[i+1:]
删除有序数组中的重复项II
题目省略了,就是现在可以最多重复两次。
改进:
1.开始的判断改为len<=2 ,因为最多可以重复两次。
2.增加一个count计数,在原if(判断两数是否相等)内层最开始判断,count大于2就什么都不做。同时增加一个else进行判断注意的是,如果不相等也要进行count赋值。
3.相等情况下,count增加1,count<2时进行赋值操作,
不相等情况下,count = 1,进行赋值操作。