Sunday, June 8, 2014

LeetCode (Python): Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

Solution:

We can obtain an algorithm that runs in $O(n)$ if we use an extra $O(n)$ space.
class Solution:
    # @param A a list of integers
    # @return an integer
    def removeDuplicates(self, A):
        aCopy =[]
        count = 0
        value = float("-infinity")
        for i in range(0, len(A)):
            if A[i] == value:
                count +=1
            else:
                count = 1
                value = A[i]
            if count <=2:
                aCopy.append(A[i])
        for i in range(0,len(aCopy)):
            A[i] = aCopy[i]
        return len(aCopy)

No comments :

Post a Comment