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

heartFollower 发布于2019-08-19 11:46 / 286人阅读

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

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

划重点：1.排序数组 2.原地删除

错误思路：
1.声明一个tmp，初始就是nums[0]，用作被比较的对象
2.用tmp去和每一个后面的数去对比，相同的跳过，不同的，先把nums[j]设成tmp,然后j++，tmp变成不同的那个数
错误点：
1.使用了新的内存空间，是错误的
2.tmp要和后面的数去比，tmp如果走到了最后一个，那么后面必然会产生越界。
3.tmp最后一定是一个和前面不同的数，这个数不参与比较，那么一定不会被覆盖写入数组
比如{1,1,2,2,3,3}->{1,2,2,2,3,3}

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0;
    int tmp = nums[0];
    for(i = 1; i < nums.length; i++)
    {
        if(nums[i] == tmp)
        {
            continue;
        }
        else
        {
            nums[j] = tmp;
            tmp = nums[i];
            j++;
        }
    }
    System.out.println(j+1);
    return j+1;
}

思路：
要求原地删除，那么一定使用快慢指针进行元素的覆盖操作。
声明两个指针，i为快指针，j为慢指针
如果遇到相同的数，那么就跳过，i++。
如果遇到不同的数，将这个值的下一个数给替换成这个不一样的值。

public static int removeDuplicates(int[] nums)
{
    int i = 0, j = 0;
    for(i = 1; i < nums.length; i++)
    {
        if(nums[j] == nums[i])
        {
            continue;
        }
        else
        {
            j++;
            nums[j] = nums[i];
        }

    }
    System.out.println(j+1);
    return j+1;
}

代码写的不够优雅，因为判断相等然后continue是没有必要的，优化一下：

public static int removeDuplicates(int[] nums)
{
    int j = 0;
    for(int i = 1; i < nums.length; i++)
    {
        if(nums[j] != nums[i])
        {
            j++;
            nums[j] = nums[i];
        }

    }
    return j+1;
}

复杂度分析：
遍历一遍，时间复杂度o(n)
空间复杂度，o(1)

私有云服务器托管 Duplicates Sorted Leetcod LeetCode

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

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

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

摘要：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。正确思路对于每一个元素，都进行移动。或者比较不到最后一个对象。给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。错误思路：由26题跳过一个的思...

haobowd 2019-08-19 11:46 评论0 收藏0
leetcode 26 Remove Duplicates from Sorted Array

摘要：题目比较简单，就是找出数组不重复的数字，返回不重复的数字个数。无需删除重复数字，只需要保证数组的前位为不重复的个数字即可代码如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...

alaege 2019-08-14 18:07 评论0 收藏0
leetcode83 Remove Duplicates from Sorted List从有序链表

摘要：题目要求从有序链表中删除重复的数字，并且返回删除后的头结点例如输入链表为返回这题和相似，只是数据结构从数组变成了链表若还有更好的思路，请多多指教想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众题目要求：从有序链表中删除重复的数字，并且返回删除后的头结点例如输入链表为1->1->2,返回1->2 这题和leetcode26相似，只是数据结构从数组变成了链表 /*...

JessYanCoding 2019-08-14 17:52 评论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
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