最长连续序列
优秀题解
https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/java-pai-xu-ji-he-ha-xi-biao-bing-cha-ji-by-lzhlyl/#%E6%96%B9%E6%B3%95%E4%B8%80%EF%BC%9A%E6%8E%92%E5%BA%8F
# Python
# 哈希: 集合实现
# 40 ms
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numset = set(nums)
max_length = 0
for num in numset:
if not num - 1 in numset: # 找到最左的数字
start_num = num
nums_len = 1
while start_num + 1 in numset: # 寻找最右的数字
start_num += 1
nums_len += 1
max_length = max(max_length, nums_len)
return max_length
# 哈希表: 字典记录 每个数组的右边界
# 2348 ms 效果差很大
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
d = dict()
for num in nums:
d[num] = num
ans = 0
for num in nums:
right_bound = d[num]
while right_bound + 1 in nums:
right_bound = d[right_bound + 1]
d[num] = right_bound
ans = max(ans, right_bound - num + 1)
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
并查集 todo
https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/java-pai-xu-ji-he-ha-xi-biao-bing-cha-ji-by-lzhlyl/#%E6%96%B9%E6%B3%95%E4%B8%89%EF%BC%9A%E5%93%88%E5%B8%8C%E8%A1%A8
1
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54