Skip to content

128 Longest Consecutive Sequence

128. Longest Consecutive Sequence

题目: https://leetcode.com/problems/longest-consecutive-sequence/

难度:

Hard

思路

首先去重复,时间O(N),然后将所有元素都放到一个字典中,这样判断一个数字的后续在不在这个字典中,如果存在就一直判断下去,每次判断只要O(1)

对于每个数,如果他的前续已经判断过了,他就没有必要判断了,继续判断下一个数,即:

if num - 1 in nums:
    continue

AC代码:

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        tmp = {}
        for num in nums:
            tmp[num] = 1
        res = 0
        for num in nums:
            if num - 1 not in nums:
                y = num + 1
                while y in nums:
                    y += 1
                res = max(res, y - num)
        return res

但其实set和字典的in判断都是O(1)

dictset实现原理是一样的,都是将实际的值放到list中。唯一不同的在于hash函数操作的对象,对于dicthash函数操作的是其key,而对于set是直接操作的它的元素,假设操作内容为x,其作为因变量,放入hash函数,通过运算后取list的余数,转化为一个list的下标,此下标位置对于set而言用来放其本身,而对于dict则是创建了两个list,一个list该下表放此key,另一个list中该下标方对应的value。参考python dict与set 的实现

其中,我们把实现set的方式叫做Hash Set,实现dict的方式叫做Hash Map/Table(注:map指的就是通过key来寻找value的过程)

setdict的唯一区别仅在于没有存储对应的value,但是,set的原理和dict一样,所以,同样不可以放入可变对象,因为无法判断两个可变对象是否相等,也就无法保证set内部“不会有重复元素”。

因此,代码也可以写成这样

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        res = 0
        for num in nums:
            if num - 1 not in nums:
                y = num + 1
                while y in nums:
                    y += 1
                res = max(res, y - num)
        return res


回到顶部