Leetcode热题100-128.最长连续序列
1. 题目描述
2. 解题思路
- 使用哈希集合的思想:
- 初始化一个
unordered_set
并将nums
中所有元素放入集合中; - 遍历数组,依次判断当前元素是否为连续序列的开始,若是则求出当前连续序列的长度;
- 依次比较得到最长连续序列。
- 初始化一个
- 使用并查集的思想:
- 将连续的数字作为一个集合,并记录当前集合元素的个数;
- 依次判断每个元素的下一个元素是否存在在同一个集合中,若存在则合并,并更新当前集合的元素个数;
- 比较得到最长连续序列。
3. 代码实现
- 哈希集合
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> set;
for (auto num : nums) {
set.insert(num);
}
int res = 0;
for (auto num : nums) {
// 当前数字为序列的起点
if (!set.count(num - 1)) {
int cur_res = 0;
while (set.count(num++))
cur_res++;
res = max(cur_res, res);
}
}
return res;
}
};
2.并查集
class Solution {
public:
// 其中cnt用于记录当前集合的元素数目
unordered_map<int, int> uf, cnt;
int find(int x) {
if (x == uf[x])
return x;
return uf[x] = find(uf[x]);
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return cnt[x];
uf[y] = x;
// 更新合并后的连通分量的元素个数
cnt[x] += cnt[y];
return cnt[x];
}
int longestConsecutive(vector<int>& nums) {
if (nums.size() == 0)
return 0;
for (auto num : nums) {
uf[num] = num;
cnt[num] = 1;
}
int res = 1;
for (auto num : nums) {
if (uf.count(num + 1)) {
res = max(res, merge(num, num + 1));
}
}
return res;
}
};
标签:cnt,return,nums,int,res,Leetcode,num,128,热题
From: https://blog.csdn.net/qewa132/article/details/141059419