Remove Duplicates from Sorted Array II
Problem
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3]
,
Your function should return length = 5
, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
Solution
Verbose Solution
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int index = 0, count = 0, cur = nums[0];
for (int num : nums) {
if (num == cur) count++;
else {
count = 1;
cur = num;
}
if (count < 3) nums[index++] = num;
}
return index;
}
}
Concise Solution
public class Solution {
public int removeDuplicates(int[] nums) {
int index = 0;
for (int num : nums) {
if (index < 2 || num != nums[index - 2]) nums[index++] = num;
}
return index;
}
}
Analysis
The first problem uses count
and cur
to check duplicates
The second solution uses formula num == nums[index - x]
where x represents the times of duplicates allow