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)

dict与set实现原理是一样的，都是将实际的值放到list中。唯一不同的在于hash函数操作的对象，对于dict，hash函数操作的是其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的过程)

set和dict的唯一区别仅在于没有存储对应的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
回到顶部