欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

python_lintcode_100删除排序数组中的重复数字 _101删除排序数组中的重复数字2

程序员文章站 2022-06-11 16:14:43
...

101删除排序数组中的重复数字

题目

给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度。

不要使用额外的数组空间,必须在原地没有额外空间的条件下完成。

样例
给出数组A =[1,1,2],你的函数应该返回长度2,此时A=[1,2]。

思路

  • 本题目比较容易出现时间限制
  • 减少for嵌套的使用
  • 不能新建数组,不能添加原数组的空间。

代码

class Solution:
    """
    @param: nums: An ineger array
    @return: An integer
    """
    def removeDuplicates(self, nums):
        # write your code here
        a=len(nums)
        if a<2:return a
        #第二个与第一个开始比较是否相同,count存放不重复数字的数量
        count=1
        for i in range(1,a):
            #重复
            if nums[i]==nums[i-1]:
                continue
            else:
            #不相同,则将放在nums的count位置
                nums[count]=nums[i]
                count+=1
        #count前都是不重复的数字
        nums=nums[:count]
        return len(nums)

101删除排序数组中的重复数字2

题目

http://www.lintcode.com/zh-cn/problem/remove-duplicates-from-sorted-array-ii/#

代码

class Solution:
    """
    @param: nums: An ineger array
    @return: An integer
    """
    def removeDuplicates(self, nums):
        # write your code here
        a=len(nums)
        if a<2:return a
        #time来标记重复的次数,count表示结果的的下标
        time=1
        count=1
        for i in range(1,a):
            #若出现重复的情况,time+1
            if nums[i]==nums[i-1]:
                time+=1
                continue
            else:
                if time>=2:
                    #出现重复的,结果应为两个重复的数,并初始化time
                    nums[count]=nums[i-1]
                    time=1
                    count+=1
                nums[count]=nums[i]
                count+=1
        #若最后几个都是重复的,则上面的循环只能标记了一个,结果需要进行补充第二个
        #处理最后部分出现两次的情况
        if nums[a-1]==nums[a-2]:
            nums[count]=nums[a-1]
            nums=nums[:count+1]
        else:
            nums=nums[:count]
        return len(nums)