对于一个以数字序列中的数字为键，出现次数为值的映射表，如何用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。
使用Guava：
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);
就是这样。（或者检查大小是否为偶数，并平均两个中心值，以更精确地说明。）
如果计数特别大，使用multiset的entrySet并保持运行总和会更快，但通常最简单的方法也可以。
ArrayList而不是使用TreeMultiset，但在现实生活中，这可能不太友好于内存。 - Kevin BourrillionTreeMultiset 实现内部使用了映射，但向您呈现了更适合您所做的事情的 API。它不是一个“简单序列”，如果您希望它是这样的话，它看起来可能像一个。 - Kevin Bourrillion线性时间
如果你知道数字的总数（在你的情况下，它是16），你可以从地图的开头或结尾开始，一直相加计数，直到达到第round(n/2)个元素，或者在和为偶数的情况下，它等于floor(n/2)和ceil(n/2)两个元素的平均值=中位数。
如果你不知道总数，那么你至少需要遍历所有数字一次。
次线性时间
如果你可以决定数据结构并且可以进行预处理，请参见维基百科关于选择算法，你可能会得到更快的次线性算法。如果你知道数据的分布情况，也可以获得次线性时间。
编辑： 因此，在我们假设有一个包含计数的序列的情况下，我们可以：
key -> count键值对并维护另一张地图 - key -> running_total这将使内存使用量增加一倍，但对于中位数，它将提供O(log n)的性能，对于total_count则为O(1)。
running_total，我只是保持了与OP相同的数据结构。 - UnreasonSortedMap，即TreeMap对于一个简单但可能不太高效的算法，我会这样做：
1. 将地图扩展为列表。
实际上，遍历地图并将键“值-次数”添加到新列表中。最后对列表进行排序。
//...
List<Integer> field = new ArrayList<Integer>();
for (Integer key:map) {
for (int i = 0; i < map.get(key); i++) {
field.add(key);
}
}
Collections.sort(field);
2. 计算中位数
现在你需要实现一个方法int calculateMedian(List<Integer> sorted)。这取决于你需要的中位数类型。如果只是样本中位数，那么结果要么是中间值（对于元素个数为奇数的列表），要么是两个中间值的平均值（对于长度为偶数的列表）。注意，列表需要排序！
（参考：样本中位数 / 维基百科）
好的，好的，尽管Chris没有提到效率，这里有一个计算样本中位数的想法（！），而不需要扩展映射...
Set<Integer> sortedKeys = new TreeSet<Integer>(map.keySet()); // just to be sure ;)
Integer median = null; // Using Integer to have a 'invalid/not found/etc' state
int total = 0;
for (Integer key:sortedKeys) {
total += map.get(key);
}
if (isOddNumber(total)) { // I don't have to implement everything, do I?
int counter = total / 2; // index starting with 0
for (Integer key:sortedKeys) {
middleMost -= map.get(key);
if (counter < 0) {
// the sample median was in the previous bin
break;
}
median = key;
}
} else {
int lower = total/2;
int upper = lower + 1;
for (Integer key:sortedKeys) {
lower -= map.get(key);
upper -= map.get(key);
if (lower < 0 && upper < 0) {
// both middlemost values are in the same bin
break;
} else (lower < 0 || upper < 0) {
// lower is in the previous, upper in the actual bin
median = (median + key) / 2; // now we need the average
break;
}
median = key;
}
}