查詢一組集合的數據結構？

Question

可以說我有一套n元素，分成若干組。每個元素都完全在一個集合中。

我希望能夠儘快做到以下查詢儘可能：

1. 什麼設置s是元素e嗎？
2. 哪些因素{e1,e2,...,ei}是集s？

我應該使用什麼數據結構？我能想到的最好的是一張指向一組套的地圖，但我想知道是否有更好的方法？

如果有幫助，你可以假設我訂的是整數{0,1,...,n-1}

Answer 1

如果您設置的是整數{0,1，...，N-1}無間隙那麼這將是更有效地使用一組數組;但是，如果整數稀疏，那麼一組地圖將需要更少的空間。無論哪種方式，操作（1）都會在恆定時間內運行（陣列的最壞情況，哈希映射的平均情況）。