用於在兩個不相交的集合上執行並集操作的數據結構

在兩個不相交的集合上，最適合用於並集操作的基本數據結構是什麼？用於在兩個不相交的集合上執行並集操作的數據結構

是否有算法可以在O（1）時間運行？

我在想一些各種各樣的哈希表，但我有點卡住了。這是一個算法和數據結構的學習指南。

全問題：設定操作UNION採用兩個不相交的集合S1和S2作爲輸入，並返回一個集合S = S1∪S2由S1和S2的所有元素（集合S1和S2是通常由此操作破壞）。解釋如何使用合適的數據結構在O（1）時間內支持UNION操作。討論您將使用哪種數據結構並描述UNION操作的算法。

來源

2015-11-02 BlazerBrown

「最好」在哪方面？還有哪些其他操作需要？只需支持工會就可以在O（1）中輕鬆完成。 – Henry

您需要說明套件應該支持的其他操作。例如，沒有固定的時間聯合，對於應該實現java.util.Set的集合。如果有人想要長時間工會，他們通常會指導你使用union-find算法（谷歌），但這與實現普通的Set接口有很大不同。 –

如果這些集合是不相交的，則鏈表（帶有頭部和尾部）就足夠了。這種情況下的聯合只是列表的連接。在C++：

struct LL { 
    Value *val; 
    LL *next; 
}; 
struct LList{ 
    LL *head; 
    LL *tail; 
};

和工會操作將是：

void unify(LList* list1, LList* list2) { 
    // assuming you take care of edge cases 
    list1->tail->next = list2->head; 
    list1->tail = list2->tail; 
    return; 
}

來源

2015-11-02 20:51:21 user1952500

一個有趣的技術，有時也適用於這個問題（並不總是不過，因爲你會看到），是利用數組「週期」，每個週期存儲一組。週期存儲爲一堆「下一個元素」鏈接，因此next[i]將給出一個表示下一個項目的整數。最後，鏈接迴環，所以這些集合必然是不相交的。

有一件好事就是你可以通過交換兩件物品來將兩件套結合在一起。

int temp = next[s1]; 
next[s1] = next[s2]; 
next[s2] = temp;

：如果你有指標s1和s2，那麼他們在（s1和s2不是特別代表，你可以參考的一組任意元素）的集合可以通過交換那些位置是被聯合或者，您可以交換您的語言。據我所知，Java並沒有很好的std::swap(&next[s1], &next[s2])。

這顯然與循環鏈表有關，但更緊湊。缺點是你必須提前準備你的「宇宙」。通過鏈接列表，您可以任意添加項目。另外，如果你的物品不是0到n的整數，那麼你將有一個陣列來完成映射，但這不是一個純粹的缺點或上升，這取決於你需要做什麼。

一個好處是，因爲你可以通過索引來引用一個項目，所以它更容易與其他數據結構結合在一起，例如它喜歡與Union Find結構（它也是一個整數數組，其中兩個），繼承兩個結構提供的O（1）聯合，保留聯合查找的攤銷O（α（n））查找，以及（從循環結構）保持O（m）集枚舉一套大小爲m。所以你大多都是兩全其美的。

在情況下，它是不是很明顯，可以用「所有singleton」像這樣初始化「宇宙」：

for (int i = 0; i < next.length; i++) 
    next[i] = i;

一樣聯盟查找。

來源

2015-11-03 09:32:43 harold

用於在兩個不相交的集合上執行並集操作的數據結構

回答

相關問題