美文网首页
LeetCode 26 快慢指针

LeetCode 26 快慢指针

作者: 何赛艾慕 | 来源:发表于2019-05-09 20:38 被阅读0次

    题目描述如下

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

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

    举几个例子

    [1,1,2]-->[1,2...],返回2
    [1,2,3,3,5]-->[1,2,3,5,..],返回4
    对于数组超出返回值序列之外的元素如何排列是不需要考虑的。

    方法一:

    没错,每次拿到题目总是想投机取巧,可能这就是算法能力那么垃圾的原因吧,不要学我。
    看到这个题目不就是删除重复元素么,于是我首先想到了使用“set”函数,于是两句话的代买就这样出来了

    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            a = list(set(nums))
            return a
    

    然后报错了,仔细审题才发现,给定的是排序数组,那么返回的也是排序数组咯,这个倒是很简单,使用“sorted”处理一下就行;还有很重要的一点,不能使用额外的数组空间。这是一个相当大的限制,不能新创建一个数组让我感觉有点麻烦,甚至觉得投机取巧的方法不成了。直到后来看到评论区大神的代码:

    class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums[:] = sorted(list(set(nums)))
        return len(nums)
    

    没错,就多了一小步而已,然而我当时就是觉得不可行,,,可能这就是蔡鸡吧。

    方法二:

    当然,上面是为了搞笑的,由于不能创建一个新数组,快慢指针是很多人都能想到的方法。简单的介绍一下快慢指针,快慢指针其实就是字面上的意思,代表的是指针前进的步数,速度不同因而得名快慢指针。很经典的快慢指针的应用如:判断单链表是否循环,寻找有序链表中位数等。
    在本题中,只要使得快指针指向重复元素的最后一个,和慢指针进行交换即可,代码如下:

    class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        n = len(nums)
        while fast < n:
            while fast < n - 1 and nums[fast] == nums[fast+1]:
                fast += 1
            nums[slow] = nums[fast]
            slow += 1
            fast += 1
        return slow 
    

    方法三

    自古评论出大神,在评论区又遇到了个四行的逆遍历的算法,先贴上再分析:

    class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in range(len(nums)-1, 0, -1):
            if nums[i] == nums[i-1]: 
                nums.pop(i)
        return len(nums)
    

    可以看到,其实思路非常简单,如果我们从顺序遍历的话,删除某个元素会影响下一个序列,再进行处理其实是有点绕的,而逆序的方法完美解决了这个问题。
    不难想,但是我在思索到正序删除不好处理序列号之后就放弃了,可见还是见识太少了,以后还是应该多思考下啊。

    相关文章

      网友评论

          本文标题:LeetCode 26 快慢指针

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