难度: Medium
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
示例 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 <= nums.length <= 104-109 <= nums[i] <= 109进阶：可以设计并实现时间复杂度为 O(n) 的解决方案吗？
注意：本题与主站 128 题相同： https://leetcode-cn.com/problems/longest-consecutive-sequence/
运行时间: 48 ms
内存: 28.7 MB
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
def findFather(num_map, i):
if num_map[i][0] !=i:
num_map[i][0] = findFather(num_map, num_map[i][0])
return num_map[i][0]
def union(num_map, i, j):
fatherI = findFather(num_map,i)
fatherJ = findFather(num_map,j)
if fatherI != fatherJ:
num_map[fatherI][0] = num_map[fatherJ][0]
num_map[fatherJ][1] += num_map[fatherI][1]
num_map = {}
for num in nums:
num_map[num] = [num, 1] # father node, count in this cluster
for num in nums:
if (num-1) in num_map:
union(num_map, num-1, num)
if (num+1) in num_map:
union(num_map, num+1, num)
res = 0
for num in num_map:
res = max(res, num_map[num][1])
return res
该题解使用了并查集的数据结构来解决问题。首先，每个数被初始化为一个集合，其中包含该数自身（作为父节点）和集合大小（初始为1）。接着，遍历所有数字，对于每个数字，检查其相邻的数字（num-1 和 num+1）是否也在数组中。如果相邻数字存在，通过union操作将当前数字与其相邻数字合并为一个集合。union操作中，确保小集合合并到大集合中，并更新集合的大小。最终，通过遍历所有数字，找到最大的集合大小，这就是最长连续序列的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
def findFather(num_map, i):
# 如果当前节点不是自己的父节点，递归找到根节点，并进行路径压缩
if num_map[i][0] !=i:
num_map[i][0] = findFather(num_map, num_map[i][0])
return num_map[i][0]
def union(num_map, i, j):
# 找到i和j的父节点
fatherI = findFather(num_map,i)
fatherJ = findFather(num_map,j)
#如果父节点不同，进行合并
if fatherI != fatherJ:
num_map[fatherI][0] = num_map[fatherJ][0]
num_map[fatherJ][1] += num_map[fatherI][1]
num_map = {}
# 初始化num_map，每个数字为一个集合
for num in nums:
num_map[num] = [num, 1] # father node, count in this cluster
# 遍历每个数字，尝试与相邻数字合并集合
for num in nums:
if (num-1) in num_map:
union(num_map, num-1, num)
if (num+1) in num_map:
union(num_map, num+1, num)
res = 0
# 找到最大的集合大小
for num in num_map:
res = max(res, num_map[num][1])
return res
题解中通过在并查集初始化时仅对输入数组 `nums` 中存在的数字建立映射来确保操作的正确性。具体操作是，遍历数组 `nums`，为每个数字在并查集中创建一个独立的集合。在后续的合并操作中，只有当检查到某数字的相邻数字（num-1 或 num+1）也在 `num_map` 中时，即它们也是数组 `nums` 中的元素，才执行合并操作。这样，只有数组中实际存在的数字才会被考虑在内，从而避免了将不存在的数字合并的问题。
路径压缩是并查集优化技术中的一种，它在执行查找操作的过程中，使得从每个节点到根节点的路径被压缩，减少了后续查找的深度。在查找节点的父节点时，路径压缩将当前节点直接连接到其根节点，这样随着越来越多的查找操作执行，整个并查集的结构越来越扁平化，减少了节点查找的层次。结果是在执行连续的并操作时，由于查找根节点的速度加快，整体上并查集的合并操作也变得更高效。这种优化显著提高了处理大数据集的能力，尤其是在连续合并操作频繁的情况下。
在并查集中，将较小的集合合并到较大的集合中是一种称为按秩合并的优化方法。这种策略可以帮助保持树的平衡，防止树结构变得过于深长，从而提高查找效率。如果总是将较小集合合并到较大的集合，那么最终形成的树的高度较低，这意味着任何节点到其根节点的路径都相对较短，从而查找操作更快。这种方法减小了树的最大高度，使得即使在多次合并后，查找节点的父节点的操作仍然可以在较低的复杂度内完成，大大提高了并查集的整体性能。