約束集

Question

開發一個項目，我需要實現一個數據集狀結構應該允許我獲得取決於minimun-maximun鍵值的子集的某些部分：

ConstainedSet <- Set((key,value)*) 
Subset <- ConstainedSet.Match(Constraint = "val1 <= key < val2") 

然後子集應該只containt那些來自的元素ConstainedSet與「val1 < = key < val2」限制匹配。也就是說，那些鍵大於或等於val1但小於val2的元素。

例如，如果我們有這樣的一個子集：

ConstrainedSet <- {(1,hand),(2,eye),(3,nose)} 

然後等的操作：

Subset <- ConstainedSet.Match(Constraint = "1 <= key < 3") 

應當的結果時，生成該子集：

Subset <- {(1,hand),(2,eye)} 

我開發一個解決方案，其中每個元素都存儲在一個三元組向量中，如

(minKey,maxKey+1,value) 

我保持這個向量由minKey和排序maxKey具有minKey順序的優先級高於maxKey順序。然後，每次調用「匹配」對該向量執行二進制搜索。

如果我沒看錯的最壞情況下的時間複雜度分別爲：

• O（N）每次調用 「匹配」。
• O（N）代表插入。

其中N是集合中元素的數量。

有沒有更好的解決方案？

Answer 1

通過密鑰將其存儲在平衡二叉樹中。

查找，插入：O（log n）。

如果您必須複製結果，那總是O（n），但如果不需要副本，則子集可以由一對「迭代器」表示，您可以返回一對最小值和最大值從樹中的節點，所以整個事情將是O（log n）。