所有操作(插入,删除,查找,find_next,find_prev)都在 log(K) 中工作 . Not log(N). So, for integer 32-bit numbers complexity is log(32)=5
缺点是内存消耗 . 需要 2^k ~ O(N) 内存,所以对于存储整数,你需要~1GB RAM . Remember, that usually O(N) memory means O(number of elements) but here it means O(maximal stored value).
2 回答
LinkedHashSet正是您要找的 . 如果你想在数组中使用索引,那么使用LinkedHashMap . 但是你需要按照从
1
到n
的顺序插入它们N
的最大值是多少?你提到你将使用正数 - Van Emde Boas tree可能是你的最佳选择 .简短的介绍:
N
所需的位数 .log(K)
中工作 . Not log(N). So, for integer 32-bit numbers complexity is log(32)=52^k ~ O(N)
内存,所以对于存储整数,你需要~1GB RAM . Remember, that usually O(N) memory means O(number of elements) but here it means O(maximal stored value).注意:我不确定支持第k个元素查询但描述看起来不错:
UPDATE
正如Dukeling在下面提到的,不支持第K个元素查询 . 我看到了实现它的唯一方法 .
在此循环之后,x将存储第k个元素 . 但复杂性是
O(K*log(bits))
. 太大的K值太糟糕了(