美文网首页
80.Remove Duplicates from Sorted

80.Remove Duplicates from Sorted

作者: 0x2333 | 来源:发表于2018-10-27 23:43 被阅读0次

    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
    

    相关文章

      网友评论

          本文标题:80.Remove Duplicates from Sorted

          本文链接:https://www.haomeiwen.com/subject/lmhetqtx.html