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: 利用集合+揪線頭法
- 基本思路是:
- 先將數(shù)字存入集合
num_set中 - 遍歷每個(gè)數(shù)字
num, 判斷它是否是線頭(即num - 1不在num_set中), 如果不是線頭, 則略過(guò), 若是線頭, 則從它開(kāi)始, 揪出以它開(kāi)頭的整根線排抬，算出長(zhǎng)度
- 分析:
- 在構(gòu)建集合的過(guò)程中, 每個(gè)數(shù)字被遍歷1次
- 在找線頭的過(guò)程中零酪，每個(gè)數(shù)字最多被遍歷2次, 最少被遍歷1次
- 因此, 每個(gè)數(shù)字最多被遍歷3次损晤，最少被遍歷2次
- 復(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
