给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
错误思路:
由26题跳过一个的思路,很自然的联想到跳过2个即可。但是对于{0,0,1,1,1,1,2,3,3}这种情况,最后一个3无法被放到前面去,结果是{0,0,1,1,2,3,2,3,3},这是因为错误代码将第一个不同的值移动到正确位置以后,下一个和刚被移动的这个值比对如果相同的话,是要等待下一次移动的,而下一次已经到了数组末尾,不再进行移动操作。
所以增加针对最后一个元素的处理(因为我只想到了最后一个元素可能和刚被移动的元素相同的情况),但是又引发了一个bug,即{1,1,1,2,2,3}->{1,1,2,2,3,3},当全部移动完成后,我会单独去比较最后一个元素是否和刚被移动的相同,相同的话,直接放到刚被正确安放的元素后,这样就导致了重复数据的出现。
public static int removeDuplicates(int[] nums){ int i = 0, j = 0, count=1; for(i = 1; i < nums.length; i++) { if(nums[i] != nums[j]) { if (count >= 2) { j = j + 2; nums[j] = nums[i]; } else { j = j + 1; nums[j] = nums[i]; } count = 1; } else { count++; } } if (nums[nums.length - 1] == nums[j]) { j = j + 1; nums[j] = nums[nums.length - 1]; } System.out.println(j+1); return j+1;}
正确思路:
public int removeDuplicates(int[] nums){ int i = 0, j = 0, count=1; for(i = 1; i < nums.length; i++) { if(nums[i] == nums[i-1]) { count++; } else { count = 1; } if (count <= 2) { j = j + 1; nums[j] = nums[i]; } } System.out.println(j+1); return j+1;}
1.对于每一个元素,都进行移动。
2.计算相同的个数,相同的数量在2个以上时,就不进行移动
3.不是比较nums[i]和nums[i+1],因为这样会导致溢出,参见26题的错误思路。或者比较不到最后一个对象。