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