|
|
1 回复 | 直到 10 年前
|
1
5
使用二进制段树。 树中的每个节点表示整数[a,b]的范围,或者是叶[a,a],或者分成两个节点,分别表示范围[a,m]和[m+1,b],其中m是(a+b)/2。 仅在必要时扩展节点,因此最初我们只有范围[0,M-1](或[0,M)的根节点(如果您愿意) 在每个节点中,统计该子树中有多少已使用/空闲的点。 插入、查找和删除x是O(logn):只需继续细分,直到到达[x,x],并更新从该节点到根的路径上的所有内容。 find_missing_key也是O(logn):因为您知道每个段的大小以及其中有多少个自由元素,所以您可以在每个节点上决定是向左还是向右,以便找到一个自由元素。 (编辑:顺便说一句,这也允许您找到第一个或最后一个,甚至第i个免费元素,而无需额外费用。) |
推荐文章