乐趣区

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 题的错误思路。或者比较不到最后一个对象。

退出移动版