前言
引用个中文社区的段子,为苦哈哈刷题增加点乐趣
我啪的一下一个sort(),很快嗷,然后一个遍历,直接通过,按传统编程,点到即止,我已经赢了。这时候他一个时间复杂度为 O(n)打过来,我大意了,没有闪,我说小力扣你不讲武德,来偷袭我这22岁的老同志,这好吗,这不好。我劝,这位小力扣耗子为汁,好好反思,不要再犯这样的错误
128. 最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
进阶:你可以设计并实现时间复杂度为 O(n) 的解决方案吗?
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
解释:最长数字连续序列是 [0 ~ 8]。它的长度为 9。
提示:
0 <= nums.length <= 104
-109 <= nums[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-consecutive-sequence
Link:https://leetcode.com/problems/longest-consecutive-sequence/
排序
O(N * logN)
排序之后,重复的数字会挨在一起,需要特殊处理。缺点是一旦排序,最优也到不了O(N)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
nums.sort()
longest = 1
current = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue
if nums[i] == nums[i - 1] + 1:
current += 1
else:
longest = max(longest, current)
current = 1
return max(longest, current)
暴力破解
O(N^2)
start, start + 1, start + 2, ... end
||
num
数字num,就看以start=num开始, 每次+1直到end不满足为止。注意边界
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longest = 0
num_set = set(nums)
for start in nums:
end = start
while end in num_set:
end += 1
longest = max(longest, end - start)
return longest
哈希
寻找起点
O(N)
在暴力破解中,每一个都作为起点单独计算,如果num - 1在哈希中,那它一定在上一个序列中,可以跳过
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 in num_set:
continue
next_num = num + 1
while next_num in num_set:
next_num += 1
longest = max(longest, next_num - num)
return longest
两端拓展
一个数字向两边寻找,如果访问过,就将记录移除
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longest = 0
record = set(nums)
for num in nums:
if num not in record:
continue
left = num - 1
while left in record:
record.remove(left)
left -= 1
right = num + 1
while right in record:
record.remove(right)
right += 1
longest = max(longest, right - left - 1)
return longest
连续边界更新
另一种思路,始终更新连续区间的左右两个边界, 例如4插入的时候:
[2, 3] 4 [5, 6, 7]
# left(连续个数) = 2, right(连续个数) = 3
# record[4] = left + right + 1
'对于新的区间[2 ~ 7]更新2|7的数值'
# record[4 - 2] = record[4]
# record[4 + 3] = record[4]
代码如下:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
record = {}
longest = 0
for num in nums:
if num in record:
continue
left = record[num - 1] if num - 1 in record else 0
right = record[num + 1] if num + 1 in record else 0
record[num] = right + left + 1
longest = max(longest, record[num])
record[num - left] = record[num]
record[num + right] = record[num]
return longest
并查集
O(N)
同样是O(N)的,哈希看起来就简单得多,但是用Union-find数据结构的好处,是可以处理流式数据。
PS: 请自行搜索”并查集”, 并查集要求完全无误默写,然鹅我已经忘记了。😭😭😭
class UnionFind:
def __init__(self, nums: list[int]):
self.ancestor = {num : num for num in nums}
self.count = {num : 1 for num in nums}
self.longest = 1 if len(nums) > 0 else 0
def find(self, node: int):
path = []
while node != self.ancestor[node]:
path.append(node)
node = self.ancestor[node]
for sub in path:
self.ancestor[sub] = node
return node
def union(self, a: int, b: int):
root_a = self.find(a)
root_b = self.find(b)
if root_a != root_b:
length = self.count[root_a] + self.count[root_b]
self.ancestor[root_a] = root_b
self.count[root_b] = length
self.longest = max(self.longest, length)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
union_find = UnionFind(nums)
num_set = set(nums)
longest = 0
for num in nums:
if num - 1 in num_set:
union_find.union(num - 1, num)
if num + 1 in num_set:
union_find.union(num, num + 1)
return union_find.longest
–End–