找出年龄流的中位数

Question

最近，有人给了我一个编码问题，其中的陈述是，我将得到一串人的年龄，然后在任何时候都会要求中位数。

像这样的东西：

add(20)
add(30)
add(30)
add(40)
getMedian() // prints 30

现在这个问题类似于这个Leetcode问题：

从数据流中查找中位数

所以我给出了2堆的方法 - 一个最大堆和一个最小堆。

面试官没有留下深刻印象，暗示可能存在优化，因为可以假设所有人的年龄都在1到130之间，而且会有很多重复的年龄，例如，有很多人的年龄在20岁。

我无法想出任何更好的优化，所以我给出了一种方法，用HashMap计算所有频率，然后计算发生次数。这是完全不正确的。

我在这里错过了什么？年龄限制如何帮助我？

编辑：

这里回答:https://stackoverflow.com/a/23603511/7134737

Answer 1

面试官可能正在寻找的方法是这样的。

保持一组频率计数。

维护数组的总计数。

维护一个变量，说明中值在哪个桶中，以及它在该桶中的第二个位置。

插入是O（1），因为您必须更新数组条目、更新总计数、更新您在中值存储桶中的位置，并且偶尔扫描固定数量的存储桶以查找下一个有条目的存储桶。

返回中值也是＜code＞O（1），因为您在一个可以查找的变量中维护该答案。

使用HashMap而不是数组只是常量因子不同。但是，必须按需计算答案的速度较慢。

请注意，此答案针对中位数进行了优化。假设我们想计算任何特定的百分比。我们可以使用不同的html" target="_blank">数据结构使其变得简单。

我会用一个257元素数组来解决这个，排列如下：

0: 0
1: Count of people aged 0
2: Count of people aged 0 or 1
3: Count of people aged 2
4: Count of people aged 0, 1, 2, or 3
5: Count of people aged 4
6: Count of people aged 4 or 5
7: Count of people aged 6
8: Count of people aged 0, 1, 2, 3, 4, 5, 6, or 7
...

一般来说，2^i*jth条目，带有j奇数，将是范围2^i*（j-1）到2^i*j-1。

为了插入一个值，我从n 1开始，跳到增加2的幂，最多8个条目。例如，如果我有一个 21 岁的用户要插入到数据结构中，我会在 22、24、32、64、125 和 256 处递增这些值。

为了计算小于或等于21的人的数量，我同样用2的幂向下看。所以我会读取 22、20、16 和 0 的值。

为了获得数据结构中的总人数，我将查看位置256中的值。

要找到一个特定的计数落在哪个年龄更复杂。我会按2的幂下降，然后进行二分查找。所以假设最终答案是21。我必须查看256、128、64、32、16，然后锁定在年龄范围0...15。然后通过查看24和20来查找16...31岁的人。这锁定了16...19岁的人。重复22、21并锁定20岁的人。我的答案是在21岁的某个地方。

在给定的示例中，此数据结构对于所有操作都是O（1），因为它具有固定的大小。但是如果您有更多的存储桶，那么所有操作都是O（log（#of桶））。