[Leetcode] Remove Duplicates from Sorted Array 移除有

kel 发布于2019-08-14 12:30 / 358人阅读

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

Remove Duplicates from Sorted Array I

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2], 
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn"t matter what you leave beyond the new length.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。具体来说，用两个指针，快指针指向当前数组遍历到的位置，慢指针指向不重复序列下一个存放的位置，这样我们一旦遍历到一个不重复的元素，就把它复制到不重复序列的末尾。判断重复的方法是记录上一个遍历到的数字，看是否一样。

代码

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) return 0;
        int dup = nums[0];
        int end = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i]!=dup){
                nums[end] = nums[i];
                dup = nums[i];
                end++;
            }
        }
        return end;
    }
}

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn"t matter what you leave beyond the new length.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

思路和上题一样，区别在于记录前两个遍历到的数字来帮助我们判断是否出现了第三遍。如果当前数字和前一个数字的前一个一样的话，说明出现了第三次。

代码

public class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length <= 2) return nums.length;
        int dup1 = nums[0];
        int dup2 = nums[1];
        int end = 2;
        for(int i = 2; i < nums.length; i++){
            if(nums[i]!=dup1){
                nums[end] = nums[i];
                dup1 = dup2;
                dup2 = nums[i];
                end++;
            }
        }
        return end;
    }
}

Follow Up 后续

Q：如果数组没有排序的话如何解？
A：可以先将其排序再用同样方法求解，然而时间复杂度将达到O(NlogN)，如果我们改用哈希表或集合来记录数字出现次数，可以用O(N)空间得到O(N)的时间。

私有云混合云 sorted-array Duplicates Sorted LeetCode

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

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

[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
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 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
LeetCode 26：删除排序数组中的重复项 Remove Duplicates from So

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...

Alan 2019-08-16 18:35 评论0 收藏0
LeetCode 26：删除排序数组中的重复项 Remove Duplicates from So

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...

cnTomato 2019-07-31 11:28 评论0 收藏0