leetcode刷题记录--【80 Remove Duplicates from Sorted Array II】

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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题的错误思路。或者比较不到最后一个对象。