80. Remove Duplicates from Sorted Array II
总结:<u>原地</u>给列表去重,最多允许K个重复值。
解法:
1.快慢指针法(做差)
描述:慢指针i是每一个结果元素的索引,快指针n遍历所有列表元素。当索引i小于K时,前面最多有K个元素重复,满足要求,故i < K
,可以直接填充元素。当前遍历的元素不等于当前i的前K个元素,因为当前i之前的元素最多有K个重复的,所以n不可能与之前元素重复,故可以填充元素 。
例子:
i = 0
for n in nums:
if( i < K or n != nums[i-K]):
nums[i]=n
i=i+1
return
2.快慢指针法(计数器)
描述:使用计数器保存重复数字出现的次数,快指针遍历,遇上不重复的就初始化计数器,遇上重复的,就检查计数器,如果为K,需要跳过当前元素,否则,保留当前元素。
例子:
if nums==[]:return 0
i=1 #慢指针 从1开始
count=1 #计数重复次数 初始为1
for j in range(1,len(nums)): #从1开始遍历
if(nums[j]==nums[j-1]):
count+=1 #有重复的 计数器就加一
if(count > K): #重复超过K个之后 就跳过当前元素
continue
else: #没重复就初始化计数器
count=1
nums[i]=nums[j] #保留当前遍历的元素
i+=1
return i
网友评论