image.png

0. 链接

题目链接

1. 题目

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

2. 思路1: 利用集合+揪线头法

1. 基本思路是:

• 先将数字存入集合num_set中
• 遍历每个数字num, 判断它是否是线头(即num - 1不在num_set中), 如果不是线头, 则略过, 若是线头, 则从它开始, 揪出以它开头的整根线，算出长度

2. 分析:

• 在构建集合的过程中, 每个数字被遍历1次
• 在找线头的过程中，每个数字最多被遍历2次, 最少被遍历1次
• 因此, 每个数字最多被遍历3次，最少被遍历2次

3. 复杂度

• 时间复杂度 O(N)
• 空间复杂度 O(N)

3. 代码

# coding:utf8
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)
        for num in num_set:
            if num - 1 not in num_set:
                cur_num = num
                cur_streak = 1
                while cur_num + 1 in num_set:
                    cur_num += 1
                    cur_streak += 1
                longest_streak = max(longest_streak, cur_streak)
        return longest_streak


def my_test(solution, nums):
    print('input: {}; output: {}'.format(nums, solution.longestConsecutive(nums)))


solution = Solution()

my_test(solution, [100, 4, 200, 1, 3, 2])
my_test(solution, [0, 0, 1, -1])
my_test(solution, [0, 0])
my_test(solution, [0, 3, 7, 2, 5, 8, 4, 6, 0, 1])

输出结果

input: [100, 4, 200, 1, 3, 2]; output: 4
input: [0, 0, 1, -1]; output: 3
input: [0, 0]; output: 1
input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]; output: 9

4. 结果

image.png