Problem: 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: Remove Duplicates from Sorted Array, Python:

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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-01 22:37:45
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @param A a list of integers
# @return an integer
def removeDuplicates(self, A):
if len(A) < 2:
return len(A)
index = 2
for i in xrange(2, len(A)):
if A[i] != A[index - 2]:
A[index] = A[i]
index += 1
return index

时间复杂度O(n),空间复杂度O(1)。