Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at mosttwice?

For example,
Given sorted arraynums=[1,1,1,2,2,3],

Your function should return length =5, with the first five elements ofnumsbeing1,1,2,2and3. It doesn't matter what you leave beyond the new length.

Remove Duplicates from Sorted Array II是Remove Duplicates from Sorted Array的升级版本，即对于一个有序数组，允许最多有两个重复元素。

一个简单直接的思路是维护一个计数器count,用来记录同一个数值元素的出现次数。出现次数为3次即以上，该元素不放入结果的有序数组中。代码如下：

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        end = 0
        length=len(nums)
        count = 1
        for i in xrange(1,length):
            temp = nums[i]
            if temp == nums[end] :
                count+=1
                if count>2:
                    continue
                end+=1
                nums[end]=temp
            else:
                count=1
                end+=1
                nums[end]=temp

        return end+1

以上代码中，end为当前结果数组的最后一位的index，也即是用来被比较的元素的index。当前元素和cur所代表的数不一样时，count重新置为1，否则加1.算法遍历了一遍数组，时间复杂度为O(n),数组inplace处理，额外空间为count,cur,temp等变量的空间，空间复杂度为O(1).

以上算法没有利用排序数字本身的特性，即连续区间首尾元素相等，则该区间所有元素相等，所以在最多只有两个重复元素时，我们可以直接比较nums[i]和nums[end-1],如果nums[i]=nums[end-1]则nums[i]=nums[end-1]=nums[end],省去了 count的计数操作，代码也大大简化：

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length=len(nums)
        if length<3:
            return length
        end = 1
        for i in xrange(2,length):
            temp = nums[i]
            if temp != nums[end-1] :
                end+=1
                nums[end]=temp

        return end+1

时间复杂度O(n),空间复杂度O(1).

优质内容筛选与推荐>>
1、Windows Minifilter驱动 - 获取进程ID, 进程名字和线程ID
2、【ContestHunter0601】Genius ACM-贪心+倍增+归并排序
3、c#操作xml增删改查
4、实现多线程的几种方式
5、代码优化——eclipse抽取相同内容

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看