26. Remove Duplicates from Sorte

【Description】

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

【Idea】
关键是在遍历时做重复值比较。

【Solution】

# solution1    暴力法
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        prev = nums[0]
        i = 1
        while i < len(nums):
            if nums[i] == prev:
                del nums[i]      # 由于del的时间复杂度为O(n)，所以运行比较慢
            else:
                prev = nums[i]
                i += 1
        return len(nums)


# solution2
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        bound = 0      # 用bound作遍历过的子列表的右下标，nums[:bound+1]中没有重复元素。时间复杂度为O(n)
        for i in range(1, len(nums)):
            if nums[i] != nums[bound]:    
                bound += 1
                nums[bound] = nums[i]
        nums = nums[:bound+1]
        return bound+1