如何计算Map <Int,Int>的中值？

Question

对于一个映射,其中键表示一个序列的数量,并且值是计数这个数字在序列中出现的频率,java中的算法实现如何计算中值？

例如:

1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7

在地图中:

Map<Int,Int> map = ...
map.put(1,2)
map.put(2,4)
map.put(3,3)
map.put(4,1)
map.put(5,1)
map.put(6,3)
map.put(7,2)

double median = calculateMedian(map);
print(median);

会导致:

> print(median);
3
>

所以我要找的是一个java实现calculateMedian.

Answer 1

线性时间

如果您知道数字的总数（在您的情况下为16），则可以从地图的开头或结尾开始，对计数进行求和，直到到达第（n / 2）个元素为止，或者总和等于第floor（n / 2）个元素和第ceil（n / 2）个元素的平均值 = 中位数。

如果您不知道总数，则必须至少对所有这些进行一次检查。

亚线性时间

如果您可以决定数据结构并可以进行预处理，请参阅维基百科有关选择算法的信息，甚至可以得到亚线性算法。如果您对数据的分布有所了解，还可以获得次线性时间。

编辑：因此，假设我们有一个计数序列，我们可以做的是

• 在插入key -> count配对时会维护另一张地图-key -> running_total
• 这样，您将拥有一个结构，通过查看最后一个键的running_total，可以得到total_count
• 并且您将能够执行二进制搜索来找到运行总计接近total_count / 2的元素

这将使内存使用量增加一倍，但对于中位数将提供O（log n）性能，对于total_count将提供O（1）。

Answer 2

使用番石榴：

Multiset<Integer> values = TreeMultiset.create();
Collections.addAll(values, 1,1,2,2,2,2,3,3,3,4,5,6,6,6,7,7);

现在，您的问题的答案是：

return Iterables.get(values, (values.size() - 1) / 2);

真。而已。 （或者检查大小是否均等，并精确计算两个中心值。）

如果计数特别大，则使用多集entrySet并保持运行总和会更快，但是最简单的方法通常很好。

Answer 3

• 使用 a SortedMap，即 aTreeMap
• 遍历map一次，计算元素总数，即所有出现次数的总和
• 再次迭代并累加出现次数，直到达到总数的一半。导致总和超过总数一半的数就是中位数
• 广泛测试相差一错误