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.
Analysis:
A wrong solution:
<When you update on a array and check on the array, you must be careful about if you get the original data or updated date>
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
if (nums.length <= 2)
return nums.length;
int count = 2;
for (int i = 2; i < nums.length; i++) {
if (nums[i] == nums[i-1] && nums[i-1] == nums[i-2])
continue;
count++;
nums[count-1] = nums[i];
}
return count;
} Problem 1:
This solution is ugly!!! The code
if (nums[i] == nums[i-1] && nums[i-1] == nums[i-2])
continue;
count++;
nums[count-1] = nums[i]; The above code could be written into:
if !(nums[i] == nums[i-1] && nums[i-1] == nums[i-2])
nums[count] = nums[i];
count++; Problem 2:
The solution has implemention logic error.
<When you update on a array and check on the same array, you must be careful about if you get the original data or updated date>
Cases:
1, 1, 1, 2, 2
After interation: i == 3,
1, 1, (2), 2, *2
At interation: i == 4
We could see
nums[4] == nums[3] && nums[3] == nums[2]
Which is wrong!!! we replaced nums[2] with 2, but nums[3] still in it's original position. We lose the information of original nums[2]. How could we solve this problem???
A great idea: check if (nums[i] != nums[count-2])
Note: the count pointer always point to the next avaiable position.
nums[count-1] means the last element we place into nums.
nums[count-2] means the last two element we place into nums. Keep on thing in mind, if the current element num[i] has already been appeared more than two times, it must be nums[count-1] and nums[count-2]. !!! And if nums[count-2] == nums[count], it means nums[count-2] must equal to nums[count-1].
If not, we could not skip it!
if (nums[i] != nums[count-2]) {
nums[count] = nums[i];
count++;
} Genius thinking!
Solution:
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
if (nums.length <= 2)
return nums.length;
int count = 2;
for (int i = 2; i < nums.length; i++) {
if (nums[i] != nums[count-2]) {
nums[count] = nums[i];
count++;
}
}
return count;
}
}