80 Remove Duplicates from Sorted Array II

1. Question

Follow up for "Remove Duplicates": What if duplicates are allowed at mosttwice?
For example, Given sorted arraynums=[1,1,1,2,2,3],
Your function should return length =5, with the first five elements ofnumsbeing1,1,2,2and3. It doesn't matter what you leave beyond the new length.

2. Implementation

1
class Solution {
2
public int removeDuplicates(int[] nums) {
3
if (nums.length <= 2) {
4
return nums.length;
5
}
6
7
int count = 1, index = 1;
8
9
for (int i = 1; i < nums.length; i++) {
10
if (nums[i - 1] != nums[i]) {
11
count = 1;
12
nums[index++] = nums[i];
13
}
14
else if (count < 2) {
15
nums[index++] = nums[i];
16
++count;
17
}
18
}
19
return index;
20
}
21
}
Copied!

3. Time & Space Complexity

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