题目描述
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given 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 respectively.
It doesn’t matter what you leave beyond the returned length. Example 2:
Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn’t matter what values are set beyond the returned length.
解题思路
这题和26题非常像，这一题也是更加加深了我对这个类型题目的理解。其实核心思想就是：用两个指针（姑且称之为指针吧），index用来定位，i用来遍历数组。实际上除了初始情况，index的值在整个过程都是作为计算长度的，而重新存入的值一直都是由index - 1指向，所以应该先比较i和index-1指向的值；再比较index - 1和index - 2的值。若两次比较都相等，则说明三个数都相等，则应该跳过当前数，i遍历下一个。
package leetcode;
public class RemoveDuplicatesfromSortedArrayII {
public int removeDuplicates(int[] nums) {
if(nums.length <= 2){
return nums.length;
}
int index = 2;
for(int i = 2; i < nums.length; i++){
if(!(nums[i] == nums[index - 1] && nums[index - 1] == nums[index - 2]))//可以简化为if(nums[i] != nums[index - 2])
{
nums[index++] = nums[i];
}
}
return index;
}
}
