Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
What if duplicates are allowed at most twice?
For example,
Given sorted array A =
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