首页 > itarticle > 26 remove duplicates from sorted array

26 remove duplicates from sorted array

admin 11月 14, 2020 0

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.

My Solution

Python

class (object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums==[]:
            return 0
        i = 0
        while i != len(nums)-1:
            for num in nums[i+1:]:
                if num > nums[i]:
                    nums[i+1] = num
                    break
            if nums[i+1] <= nums[i]:
                break
            i = i+1
        return i+1

Best Solution

Python

class :
    
    # @return an integer
    def removeDuplicates(self, A):
        if not A:
            return 0
        newTail = 0
        for i in range(1, len(A)):
            if A[i] != A[newTail]:
                newTail += 1
                A[newTail] = A[i]
        return newTail + 1

想法：O(n)，本质上和我的方法一致
range(n,m)：n到m-1的整数，即[n,m)