|
Given an unsorted array of integers?nums, return?the length of the longest consecutive elements sequence.
You must write an algorithm that runs in?O(n)?time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <= nums.length <= 105-109?<= nums[i] <= 109
这道题有很多解法，比如通过排序或者使用Hashmap。但是通过分析题目就会发现这题还可以使用并查集（Union Find）来解答。
我们知道并查集（Union Find）是解决连通性问题和处理集合的合并与查找问题。题目要求是从一个未排序的数组中查找一个最长的连续数的序列，其实就是合并连续的数，然后查找最长连续数序列，刚好满足并查集特性。
算法实现：
1）数组里的所有数看成一个单点集合，
2）然后根据数之间是否连续的连通特性，把所有连续数并成一个集合
3）最后最大那个集合就是我们要找的最长连续数序列。
class UnionFind:
def __init__(self):
self.parent = {} #由于数值不连续大小不定可能很大所以这里用字典而不用数组
self.size = {} #用于记录数所在集合的大小，提高合并查找的效率
self.maxsize = 0 #用于记录最大集合里的数的个数
#查找一个数的父节点
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def merge(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return
if self.size[px] > self.size[py]:
self.parent[py] = px
self.size[px] += self.size[py]
self.maxsize = max(self.maxsize, self.size[px])
else:
self.parent[px] = py
self.size[py] += self.size[px]
self.maxsize = max(self.maxsize, self.size[py])
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
uf = UnionFind()
#输入数组为空返回长度为0否则长度至少为1
uf.maxsize = 0 if len(nums) == 0 else 1
for num in nums:
#与到一个新数先作为一个单点集合存入，重复出现的数可不做处理
if num not in uf.parent:
uf.parent[num] = num
uf.size[num] = 1
#用当前数分别加1和减1去寻找是否已经存在，如果是则进行合并
if num - 1 in uf.parent :
uf.merge(num, num - 1)
if num + 1 in uf.parent:
uf.merge(num, num + 1)
return uf.maxsize
|