我正在解決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熱心網友回復：
是對的。具有路徑壓縮的正確實施的聯合查找具有攤銷的線性運行時間復雜度。
關鍵部分是路徑壓縮，它發生在您的代碼中：
return parent[i]=find(parent[i])
與不使用路徑壓縮的以下內容相比：
return find(parent[i])
這部分代碼的作用是扁平化層次結構中的節點結構，并將每個節點直接鏈接到最終根。只有在第一次運行時，find您才會遍歷整個結構。下次您將直接命中，因為您將節點的父節點設定為其最終根。請注意，第二個代碼片段作業得非常好，但是當您對路徑本身不感興趣并且只對最終根感興趣時，它只會做多余的作業。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/442159.html
上一篇：SFML：當我按下一個鍵時，影像被繪制并移動，但當我嘗試創建它們的矢量時不移動
下一篇：嘗試在向量中使用成員類時出錯