我正在寻找一种在 STL 中存储整数的数据结构。
我要支持的主要操作是插入和删除,查找前20个元素,以及查找任意k的第k大元素。
我知道使用集合,我可以在 log N 时间内实现插入和删除,在 O(1) 时间内实现前 20 个,在 O(k) 时间内实现前 k 个。
有没有什么方法可以选择一个可能有更好的能力找到前k个条目的数据结构?例如,选择 k = N/2——中位数——使用一个集合需要 O(N) 时间,但理想情况下我们可以有更好的东西。
哈希表在 o(1) 时间内完成插入、删除和搜索。所以这个