我有一個專案，我必須用路徑壓縮演算法實作加權快速聯合。在看到其他一些源代碼后，我最終得到了：
public class UnionFind {
private int[] parent;
private int[] size;
private int maxItemCount; // maximum number of items from {0,1,...,N-1}
private int numItems; // number of items created
UnionFind(int N) {
this.N = N;
this.K = 0;
parent = new int[N];
size = new int[N];
for (int i = 0; i < N; i ) {
parent[i] = -1;
size[i] = 0;
}
}
void makeSet(int v) {
if (parent[v] != -1) return; // item v already belongs in a set
parent[v] = v;
size[v] = 1;
K ;
}
int find(int v) {
if (v == parent[v]) {
return v;
}
return parent[v] = find(parent[v]);
}
void unite(int v, int u) {
int x=find(v);
int y=find(u);
if(x!=y) {
parent[x]=y;
}
}
int setCount() {
int item=0;
for(int i=0;i<parent.length;i ) {
if(i==parent[i]) {
item ;
}
}
return item; // change appropriately
}
int itemCount() {
return K;
}
分配給我的任務是正確完成以下方法：
- 整數查找（整數 v）
- 無效聯合（int v，int u）
- setCount(int v)
好吧，演算法似乎很慢，我找不到合適的解決方案。
uj5u.com熱心網友回復：
這里有一些問題：
該
size資訊未使用，但該資訊對于保持所需性能至關重要。最重要的是，在unite：size應該保持更新：聯合集將擁有與兩個給定集一樣多的成員size應該確定兩個根節點中的哪一個應該是聯合集的根，因為這將使樹保持平衡
setCount具有 O(n) 時間復雜度。如果您在成員變數中跟蹤該數字，它可以在 O(1) 時間內提供資訊。我會呼叫它numSets。如果setCount()呼叫很多，這種變化將產生積極的影響。
不是問題，但是將變數命名為NandK并無助于使代碼可讀。為什么不給出實際說明它們是什么的名稱，這樣您就不需要在它們的定義中附上注釋來給出解釋？
這是您進行這些修改的代碼：
public class UnionFind {
private int[] parent;
private int[] size;
private int maxItemCount;
private int numItems;
private int numSets;
UnionFind(int maxItemCount) {
this.maxItemCount = maxItemCount;
numItems = 0;
numSets = 0;
parent = new int[maxItemCount];
size = new int[maxItemCount];
for (int i = 0; i < maxItemCount; i ) {
parent[i] = -1;
size[i] = 0;
}
}
void makeSet(int v) {
if (parent[v] != -1) return; // item v already belongs in a set
parent[v] = v;
size[v] = 1;
numItems ;
numSets ; // Keep track of number of sets
}
int find(int v) {
if (v == parent[v]) {
return v;
}
return parent[v] = find(parent[v]);
}
void unite(int v, int u) {
int x = find(v);
int y = find(u);
if (x != y) {
numSets--; // A union decreases the set count
// Determine which node becomes the root
if (size[x] < size[y]) {
parent[x] = y;
size[y] = size[x]; // Adapt size
} else {
parent[y] = x;
size[x] = size[y]; // Adapt size
}
}
}
int setCount() {
return numSets; // Kept track of it
}
int itemCount() {
return numItems;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520471.html
標籤：爪哇算法联合发现