并查集的相关知识: c++ 并查集实现优化
128. 最长连续序列
// hard
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
- 要求复杂度O(N)， 一般就是使用空间换时间，可以考虑使用 hash_map 记录
Hash
具体做法
- 用哈希表存储每个端点值对应连续区间的长度
- 若数已在哈希表中：跳过不做处理
- 若是新数加入：
- 取出其左右相邻数已有的连续区间长度 left 和 right
- 计算当前数的区间长度为：cur_length = left + right + 1
- 根据 cur_length 更新最大长度 max_length 的值
- 更新区间两端点的长度值
int longestConsecutive(vector<int>& nums) {
int len = nums.size();
int res = 0;
if(!len) return res;
unordered_map<int,int> hash;
for(int i=0;i<len;i++){
int left = 0,right = 0,cur = 0;
if(hash.find(nums[i])!=hash.end()) continue;
if(hash.find(nums[i]-1)!=hash.end()) left = hash[nums[i]-1];
if(hash.find(nums[i]+1)!=hash.end()) right = hash[nums[i]+1];
hash[nums[i]] = left + right + 1;
// 更新左右区间边界数的 长度，虽然中间数的长度也变了，但是不影响结果
hash[nums[i]-left] = hash[nums[i]];
hash[nums[i]+right] = hash[nums[i]];
res = max(hash[nums[i]],res);
}
return res;
}
1. 建立hash, 同时，我们只对 当前数字 - 1 不在哈希表里的数字，作为连续序列的第一个数字去找对应的最长序列，这是因为其他数字一定已经出现在了某个序列里。
int longestConsecutive(vector<int>& nums) {
int len = nums.size(),res=0;
if(!len) return res;
unordered_set<int> hashset(nums.begin(),nums.end());
for(int i=0;i<len;i++){
if(hashset.count(nums[i]-1) == 0){
int x = nums[i];
while(hashset.count(x)) x++;
res = max(res,x-nums[i]);
}
}
return res;
}
并查集
class UnionFind{
public:
unordered_map<int,int> parent;
unordered_map<int,int> cnt;
public:
UnionFind(vector<int> nums){
for(int i=0;i<nums.size();i++){
parent[nums[i]] = nums[i];
cnt[nums[i]] = 1;
}
}
int find(int p){
if(p != parent[p]) parent[p] = find(parent[p]);
return parent[p];
}
void unionelem(int p,int q){
int proot = find(p);
int qroot = find(q);
if(proot != qroot){
parent[proot] = qroot;
cnt[qroot] += cnt[proot];
}else return;
}
};
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int len = nums.size(),res=0;
if(!len) return res;
UnionFind uf(nums);
for(auto num:nums){
if(uf.parent.find(num+1) != uf.parent.end()){
uf.unionelem(num,num+1);
}
}
for(auto elem:uf.cnt){
res = max(res,elem.second);
// cout<<res<<endl;
}
return res;
}
};
1319. 连通网络的操作次数
并查集
- 创建一个并查集，和集合的个数
- 进行合并操作union,如果合并成功，集合个数减1 -1
- 如果合并失败，说明这两个计算机已经在一个集合中，即 这个链接是一个多余的边，记录多余边的个数
- 最后遍历完后， 统计 集合个数 和 多余边数，每一个 多余边 可以消除(链接)一个集合
集合个数==1，表示都在一个集合中，全都可以互相链接 返回0
如果 多余边数 < 集合个数-1 则不能全部链接 返回-1
如果可以链接，直接返回 集合个数-1, 即全部链接需要的最小边数
class UnionFind{
private:
int* parent;
public:
int cnt;
UnionFind(int n):parent(new int[n]),cnt(n){
for(int i=0;i<n;i++){
parent[i] = i;
}
}
int find(int p){
if(p != parent[p]) parent[p] = find(parent[p]);
return parent[p];
}
bool unionelem(int p,int q){
int proot = find(p);
int qroot = find(q);
if(proot != qroot){
parent[proot] = qroot;
cnt-=1;
return true;
}else return false;
}
};
class Solution {
public:
int makeConnected(int n, vector<vector<int>>& connections) {
if(!connections.size()) return 0;
UnionFind uf(n);
int count = 0;
for(int i=0;i<connections.size();i++){
if(!uf.unionelem(connections[i][0],connections[i][1])) count+=1;
}
if(uf.cnt == 1) return 0;
if(count < uf.cnt - 1) return -1;
return uf.cnt-1;
}
};
547. 朋友圈
class UnionFind{
private:
int* parent;
public:
int cnt;
UnionFind(vector<vector<int>> M){
int n=M.size();
parent = new int[n];
cnt = n;
for(int i=0;i<n;i++)
parent[i] = i;
}
int find(int p){
if(p!=parent[p]) parent[p] = find(parent[p]);
return parent[p];
}
void union_elem(int p,int q){
int proot = find(p);
int qroot = find(q);
if(proot!=qroot){
parent[proot] = qroot;
cnt -= 1;
}
}
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if(!M.size()) return 0;
int n=M.size(),m=M[0].size();
UnionFind uf(M);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i!=j && M[i][j] == 1){
uf.union_elem(i,j);
}
}
}
return uf.cnt;
}
};
684. 冗余连接
class Solution {
public:
int* parent;
int* rank;
// int find(int a){
// if(parent[a] != a) parent[a] = find(parent[a]);
// return parent[a];
// }
int find(int a){
int p=a,t;
while(parent[p] != p) p = parent[p];
while(a != p){
t = parent[a];
parent[a] = p;
a = t;
}
return parent[a];
}
bool isConnect(int a, int b){
return find(a) == find(b);
}
bool unionelem(int a,int b){
int aroot = find(a);
int broot = find(b);
if(aroot != broot){
if(rank[aroot] < rank[broot]){
parent[aroot] = broot;
}else{
parent[broot] = aroot;
if(rank[aroot] == rank[broot]) ++rank[aroot];
}
return false;
}else return true;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
vector<int> res;
int len = edges.size();
if(!len) return res;
parent = new int[len+1];
rank = new int[len+1];
for(int i=0;i<=len;i++){
parent[i] = i;
rank[i]=0;
}
unionelem(edges[0][0],edges[0][1]);
for(int i=1;i<len;i++){
if(unionelem(edges[i][0],edges[i][1])){
res.push_back(edges[i][0]);
res.push_back(edges[i][1]);
break;
}
}
return res;
}
};
947. 移除最多的同行或同列石头
c++ 并查集 ，看了大佬的思路，才知道可以把行列 合并起来，=_= , 我是按照同行同列将 石头链接起来，看存在几个集合，每个集合都可以删除到最后一个石头，所以可删除的石头就是 总石头数 - 集合数
class DSU{
public:
int* parent;
int cnt;
DSU(int n):parent(new int[n]),cnt(n){
for(int i=0;i<n;i++) parent[i] = i;
}
int find(int a){
if(a != parent[a]) parent[a] = find(parent[a]);
return parent[a];
}
void union_elem(int a,int b){
int aroot = find(a);
int broot = find(b);
if(aroot!=broot){
parent[aroot] = broot;
cnt-=1;
}
}
};
class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
int n = stones.size();
if(!n) return 0;
DSU uf(n);
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
if(stones[i][0] == stones[j][0] ||
stones[i][1] == stones[j][1]){
uf.union_elem(i,j);
}
}
}
return n-uf.cnt;
}
};
京公网安备 11010502036488号