128. 最长连续序列

题目链接

解题思路：难点在于时间复杂度O(n)，如果直接排序，题目就简单了。但是不需要全部有序，只需要每次从其中拿出一个数，是递增的即可，也就是说，使用优先级队列，堆头是最小值。注：该方法仍然是O(n*logn)

代码

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        pq = []
        ans = 0
        for i in range(len(nums)):
            heapq.heappush(pq, nums[i])
        cur = 1
        pre_num = heapq.heappop(pq)
        while pq:
            tmp = heapq.heappop(pq)
            if tmp == pre_num:
                continue
            if pre_num == tmp - 1:
                cur += 1
                pre_num = tmp
            else:
                ans = max(ans, cur)
                cur = 1
                pre_num = tmp
        ans = max(ans, cur)
        return ans

方法二：把所有数加入到集合，每次从集合中取出一个数x，我们期望的是找到x+1，找到x+1后，我们期望找到x+2，所以用一个while循环即可。

• 这里面代码有优化，当我们找到一连串的x, x+1, x+2, ... , x+k时，再从x+1开始时，就不用找了，因为找过一遍了

• 代码

  class Solution:
      def longestConsecutive(self, nums: List[int]) -> int:
          if not nums:
              return 0
          nums_set = set(nums)
          ans = 0
          for num in nums_set:
              if num - 1 not in nums_set:    # 避免重复计算
                  cur_num = num
                  cur_len = 1
                  while cur_num + 1 in nums_set:
                      cur_num += 1
                      cur_len += 1
                  ans = max(ans, cur_len)
          return ans