我正在解決LeetCode 上的一個問題：
給定一個未排序的整數陣列
nums，回傳最長連續元素序列的長度。你必須撰寫一個O(n)及時運行的演算法。所以對于nums=[100,4,200,1,3,2]，輸出是4。
解決此問題的 Union Find 解決方案如下：
class Solution {
public:
vector<int> parent, sz;
int find(int i) {
if(parent[i]==i) return i;
return parent[i]=find(parent[i]);
}
void merge(int i, int j) {
int p1=find(i);
int p2=find(j);
if(p1==p2) return;
if(sz[p1]>sz[p2]) {
sz[p1] =sz[p2];
parent[p2]=p1;
} else {
sz[p2] =sz[p1];
parent[p1]=p2;
}
}
int longestConsecutive(vector<int>& nums) {
sz.resize(nums.size(),1);
parent.resize(nums.size(),0);
iota(begin(parent),end(parent),0);
unordered_map<int, int> m;
for(int i=0; i<nums.size(); i ) {
int n=nums[i];
if(m.count(n)) continue;
if(m.count(n-1)) merge(i,m[n-1]);
if(m.count(n 1)) merge(i,m[n 1]);
m[n]=i;
}
int res=0;
for(int i=0; i<parent.size(); i ) {
if(parent[i]==i && sz[i]>res) {
res=sz[i];
}
}
return res;
}
};
這被 OJ 接受（運行時間：80毫秒，比76.03%最長連續序列的 C 在線提交更快），但這真的像許多答案所O(n)聲稱的那樣嗎？我的理解是 Union Find 是一種 O(NlogN) 演算法。
他們是對的嗎？或者，我錯過了什么？
uj5u.com熱心網友回復：
他們是對的。具有路徑壓縮和按等級聯合的正確實施的聯合查找具有整體線性運行時間復雜度，而任何單個操作具有攤銷的恒定運行時間復雜度。任何型別的操作的確切復雜性是反阿克曼函式在哪里。對于物理世界中的任何可能，逆阿克曼函式不超過 4。因此，我們可以說單個操作是恒定的，而演算法作為一個整體是線性的。mO(m * alpha(n))alphan
代碼中路徑壓縮的關鍵部分在這里：
return parent[i]=find(parent[i])
與不使用路徑壓縮的以下內容相比：
return find(parent[i])
這部分代碼的作用是扁平化層次結構中的節點結構，并將每個節點直接鏈接到最終根。只有在第一次運行時，find您才會遍歷整個結構。下次您將直接命中，因為您將節點的父節點設定為其最終根。請注意，第二個代碼片段作業得非常好，但是當您對路徑本身不感興趣并且只對最終根感興趣時，它只會做多余的作業。
等級聯盟在這里很明顯：
if(sz[p1]>sz[p2]) {...
它確保具有更多子節點的節點成為具有較少子節點的節點的根。因此，需要為新父節點重新分配的節點更少，因此作業量更少。
注意：以上內容已根據@Matt-Timmermans 和@kcsquared 的反饋進行了更新和更正。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/443792.html
下一篇：此集合實體上不存在屬性[組]