1

我们必须将整数一个接一个地输入到一个数组中。在输入过程进行时，我们可能会被要求从数字的顶部（最大）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

我的方法是应用带有分区的选择算法，但是已经超过了时间限制。

4

3 回答 3

3

为什么选择算法失败：
请注意，在#elements 中使用选择算法是线性的。假设 #requests 在 #elements 中是线性的 - 这将导致二次解，这就是您超出时间限制的原因。

另一种方法： 维护两个堆：一个最大堆H1和一个最小堆H2

最大堆 ​​( H1) 将保存 2/3 的最低数字，而最小堆将保留 1/3 的最高数字。

现在，对于您读取的每个元素x，检查是否需要增加顶部 1/3 堆 ( H2)，如果需要：您需要添加max{x,H1.max()}. 如果您添加了H1.max()- 您需要将其从堆中删除，然后插入x。如果不需要添加，则检查是否x大于 then H2.min()，如果是，则删除 min 形式H2，将其插入H1，然后添加x到H1。


注意：您在此解决方案中查找的数字可以随时找到O(1)，它是最小堆 ( H2) 的最小值。

如果此解决方案的总复杂度是O(nlogn + k)-n数字的数量在哪里，并且k是“告诉数字”请求的总数。

注意：一个更简单的解决方案（虽然可能更慢）是保持列表排序（例如在BST或跳过列表中），并使用二进制搜索来查找相关元素。

例子：

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
于 2012-07-09T12:13:08.053 回答
0

怎么样：

  1. 保持数组有序，插入成本 = log(n)
  2. 从 1/3 = O(1) 中获取最小值
于 2012-07-09T18:15:11.320 回答
0

（我认为这个问题是某种家庭作业（“我们必须”），因此我没有直接给出答案。）

重新制定你的任务：你被要求使用在线算法找到第 66 个百分位。中位数已经有一个 SO 问题，即第 50 个百分位数，因此您应该能够从那里适应。如果该算法不好，请对在线中值算法进行一些研究，其中大部分也应该适用于您的问题。

于 2012-07-09T11:59:13.043 回答