美文网首页算法学习打卡计划
leetcode第二十六题 —— 删除排序数组中的重复项

leetcode第二十六题 —— 删除排序数组中的重复项

作者: 不分享的知识毫无意义 | 来源:发表于2019-12-02 18:46 被阅读0次

1.题目

原题:

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

例子:

给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, 
并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

2.解析

这道题读题是关键,题目要求返回不重复值的长度。此外还要求把不重复值放在列表的前边,后边超出的部分保留列表的原值。
这道题实现方式很多种:

  • 用set,值得注意的是python set是给你去重了,但遇到负数默认就把它放到正数后边了,因此需要再进行一次sort排序。
  • 自己思考逻辑,很多实现方案,我想的是设置两个下标i,j,while循环,如果相等的话j+1,不相等的话把不相等的值赋值给当前位置i的下一个值,如此循环直到遍历完整个列表。
    网上还有很多其他的思路,其实都差不多,就是找到循环的方法,自己有想法也可以写一下调试一下。

3.python代码

3.1 set方法

class Solution(object):
    def removeDuplicates(self, nums):
        new_nums = list(set(nums))
        new_nums.sort()
        nums[:len(new_nums)] = new_nums
        return len(new_nums)

3.2 双下标方法

class Solution(object):
    def removeDuplicates(self, nums):
        i = 0
        j = 1
        while i < len(nums) and j < len(nums):
            if nums[i] == nums[j]:
                j += 1
            else:
                nums[i+1] = nums[j]
                i += 1
        return i+1

相关文章

网友评论

    本文标题:leetcode第二十六题 —— 删除排序数组中的重复项

    本文链接:https://www.haomeiwen.com/subject/gjxfgctx.html