algorithm - 类似于数组但支持删除的数据结构

Question

我正在考虑以下数据结构问题：

给定整数之间1并按n排序顺序，每个操作都会查询然后删除（在一次调用中）k第一个最小的数字。如何使查询和删除都是常数时间操作？

它类似于数组结构，但需要不断删除。虽然顺序平衡二叉树可以做到这一点，但它很O(lg n)复杂。

可以利用 range 属性（仅在1和之间的数字n）使其工作吗？

Answer 1

LinkedHashSet是您正在寻找的。如果您想要数组中的索引，请使用此LinkedHashMap。但是您需要按照从1到的顺序插入它们n

Answer 2

的最大值是N多少？您提到您将使用正数 - Van Emde Boas 树可能是您的最佳选择。

简短描述：

- 允许仅存储来自 [0,2^k) 的正数，其中 k 是存储最大数所需的位数N。
- 所有操作（插入、删除、查找、find_next、find_prev）在log(K). 不是日志（N）。因此，对于整数 32 位数字，复杂度为 log(32)=5
- 缺点是内存消耗。需要2^k ~ O(N)内存，因此要存储整数，您需要 ~1GB RAM。请记住，通常 O(N) 内存意味着 O（元素数量），但在这里它意味着 O（最大存储值）。

注意：我不确定是否支持第 k 个元素查询，但描述看起来不错：

FindNext：找到至少给定k个最小键的键/值对

FindPrevious：在给定的 k 内找到最大键的键/值对

更新

正如下面提到的 Dukeling，不支持第 K 个元素查询。我看到了实现它的唯一方法。

int x = getMin();
for(int i=0;i<k-1;i++) x = getNext(x);

在这个循环之后 x 将存储第 k 个元素。但复杂性是O(K*log(bits)). 对于较大的 K 值来说太糟糕了（