Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
Question Name: Remove Duplicates from Sorted Array II
The second previous element might be overwritten in the last round.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: # @param A a list of integers # @return an integer def removeDuplicates(self, A): if len(A) < 3: return len(A) front, back = 2, 2 secondPre = A[front-2] while front < len(A): if A[front] == A[front-1] and A[front] == secondPre: secondPre = A[front-1] else: secondPre = A[front-1] A[back] = A[front] back += 1 front += 1 return back |
Well, inspired by http://www.mitbbs.com/article_t/JobHunting/32770131.html, there is a better and more generic solution as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | class Solution: # @param A a list of integers # @param M the times that duplicates are allowed # @return an integer def _removeDuplicatesHelper(self, A, M): ''' Remove some duplicate items in A. So that one single item appears at most M times. ''' if len(A) < 2: return len(A) toWrite = 1 # The position for next write. And toWrite - 1 # is th previous appeared item. count = 1 # The occurrence of previous appeared item. for index in xrange(1, len(A)): if A[index] == A[toWrite-1]: # Is a duplicate item, being the same as the previous one. count += 1 if count <= M: # It is allowed to appear M times or less. A[toWrite] = A[index] toWrite += 1 else: # Meet with a new item. A[toWrite] = A[index] toWrite += 1 count = 1 return toWrite # @param A a list of integers # @return an integer def removeDuplicates(self, A): return self._removeDuplicatesHelper(A, 2) |
With the parameter M in _removeDuplicatesHelper, we could solve all the problems, which allow the occurrence at most M times.