高效的群組查找數據結構


0

我需要一個數據結構,該結構允許有效查詢"給我x組"。

讓我給你舉個例子:

Group 1: [a, b, c] 
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -> [d, e]

對存儲或構建時間沒有明顯的限制。我只需要getGroupOfO(logn)或更快。

我正在考慮使用Dictionary<Element, Set<Element>>,其中組中所有元素的條目共享相同的集合引用。這將根據字典的實現有效地使查找O(1)O(logn)有效,但是會導致很多條目。

這感覺有點腫,我想知道:是否有一個更優雅的數據結構來實現這一目標?

編輯:組中的元素可以完全任意,並且沒有順序。

0

If the groups are static, your data structure is perfectly reasonable.

You can also consider the Union-Find data structure. Find is the getGroupOf operation. It is quite fast, and also allows you to modify the data structure by merging groups and adding a new item in its own group.