我们必须将整数一个一个地输入到数组中。在输入过程中，我们可能会被要求从顶部(最大)1/3 的数字中找到最小的数字，任意次数.
例如:
input 1
input 7
input 9
tell the number
input 21
input 8
input 5
tell the number
input 11
tell the number
输出应该是:
9
9
11
解释:
- 直到第一个查询，数组中的数字将是 1 7 9，因此前 1/3 的数字将是 9。因为它们只有一个数字，所以它也是最小的。
- 当进行第二个查询时，数组看起来像
1 7 9 21 8 5，因此对数组进行排序时:21 9 8 7 5 1，前 1/3 的数字将是 21 和 9。其中最小的 将是 9 - 在最终查询数组中有
1 7 9 21 8 5 11，排序21 11 9 8 7 5 1前 1/3 数字将是 21 和 11 . 其中最小的是 11。
数组中的整数总数可以是250000
我的方法是应用带分区的选择算法，但它已超过时间限制。
最佳答案
为什么选择算法失败:
请注意，在#elements 中使用选择算法是线性的。假设#requests 在#elements 中是线性的——这将导致二次解，这就是为什么你会超过时间限制。
另一种方法:
维护两个堆:最大堆 H1 和最小堆 H2
最大堆 (H1) 将保留 2/3 的最低数字，而最小堆将保留 1/3 的最高数字。
现在，对于您读取的每个元素 x，检查您是否需要增加顶部 1/3 堆 (H2)，如果需要:您需要添加 max{x,H1.max()}。如果您添加了 H1.max() - 您需要将其从堆中移除，然后插入 x。如果不需要加法，检查x是否大于H2.min()，如果是，去掉min形式H2，插入它到H1，并将x添加到H1。
注意:这个解中你要找的数随时都可以在O(1)中找到，它是min heap (H2 )。
如果此解决方案的总复杂度为 O(nlogn + k) - 其中 n 是数字的数量，k 是总数“说出数字”请求的数量。
注意:一个更简单的解决方案(虽然可能更慢)是保持列表排序(例如在 BST 或 skiplist 中)，并使用二进制搜索来查找相关元素。
示例:
init:
H1 = {}
H2 = {}
input1:
H1 = {1}
H2 = {}
input7:
H1={1,7}
H2 = {}
input 9: //need to add a max, in this case: x > H2.max() -> add x to H2.
H1 = {1,7}
H2 = {9}
tell the number
H2.min() = 9
input 21: // 21>9 -> remove H2.min() add it to H1, add x to H2
H1 = {1,7,9}
H2 = {21}
input 8:
H1 = {1,7,8,9}
H2 = {21}
input 5: //remove max from H1, add max to H2, add x to H1
H1 = {1,7,5,8}
H2 = {9,21}
tell the number
H2.min() = 9
input 11: //remove min from H2, add it to H1, add x to H2.
H1 = {1,7,5,8,9}
H2 = {11,21}
tell the number
H2.min() = 11
关于algorithm - 分区选择算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11394503/