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: 利用集合+揪線(xiàn)頭法

1. 基本思路是:

• 先將數(shù)字存入集合num_set中
• 遍歷每個(gè)數(shù)字num, 判斷它是否是線(xiàn)頭(即num - 1不在num_set中), 如果不是線(xiàn)頭, 則略過(guò), 若是線(xiàn)頭, 則從它開(kāi)始, 揪出以它開(kāi)頭的整根線(xiàn)，算出長(zhǎng)度

2. 分析:

• 在構(gòu)建集合的過(guò)程中, 每個(gè)數(shù)字被遍歷1次
• 在找線(xiàn)頭的過(guò)程中，每個(gè)數(shù)字最多被遍歷2次, 最少被遍歷1次
• 因此, 每個(gè)數(shù)字最多被遍歷3次，最少被遍歷2次

3. 復(fù)雜度

• 時(shí)間復(fù)雜度 O(N)
• 空間復(fù)雜度 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])

輸出結(jié)果

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. 結(jié)果

image.png