leetcode刷题记录--【80 Remove Duplicates from Sorted Ar

haobowd 发布于2019-08-19 11:46 / 2736人阅读

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。正确思路对于每一个元素，都进行移动。或者比较不到最后一个对象。

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

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

混合云私有云 Duplicates Sorted Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77854.html

leetcode刷题记录-【26 Remove Duplicates from Sorted Ar

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用额外空间的条件下完成。声明两个指针，为快指针，为慢指针如果遇到相同的数，那么就跳过，。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组...

heartFollower 2019-08-19 11:46 评论0 收藏0
leetcode80. Remove Duplicates from Sorted Array II

摘要：思路与代码其实在这里我们仍然延续中的思路。在遇到非重复值以及非多余的重复值时，将数值移动到当前记录的下标上。保证该下标前的值均为满足题目条件的值。第一次我使用了来记录某个值出现的次数。题目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...

CoderDock 2019-08-15 10:42 评论0 收藏0
[Leetcode] Remove Duplicates from Sorted Array 移除有

摘要：双指针法复杂度时间空间思路我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。代码双指针法复杂度时间空间思路思路和上题一样，区别在于记录前两个遍历到的数字来帮助我们判断是否出现了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...

kel 2019-08-14 12:30 评论0 收藏0
[LintCode/LeetCode] Remove Duplicates from Sorted

摘要：思路原数组长度为，则返回原数组长度不为，则至少有个元素。将所有不重复的数值赋给，而当和相等时，不做处理。最后返回的就是不同元素的个数，也是新数组的长度。只有在时，才对赋值。注意，每次初始化的时候要分两种情况，这就意味着从的时候开始遍历。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...

WalkerXu 2019-08-14 15:32 评论0 收藏0
leetcode82. Remove Duplicates from Sorted List II

摘要：题目要求翻译将链表中重复的元素全部删除，返回新的头结点。相比于，这里将重复的元素全部删除。除此以外，我们还需要知道重复元素的前一个值和重复元素的最后一个值。如果存在重复值，则跳过重复值后，前节点不变，否则前节点跟随后节点同时向后移动。题目要求 Given a sorted linked list, delete all nodes that have duplicate number...

崔晓明 2019-08-15 10:36 评论0 收藏0