algorithm - 计算给定输入数据的中值及其频率

Question

我得到以下输入:

num: counts
1:5
2:4
3:8

这是数频比:

为了计算这个输入的中位数，我采用了一种天真的方法，即用这些元素填充一个数组

>>>l = [1,1,1,1,1,2,2,2,2,3,3,3,3,3,3,3,3]
>>>i = len(l)/2
>>> median = l[i] if not i%2 else l[i+1]
>>> median
2

这是正确的。但是，我不必要地使用数组来填充。我想知道是否有一种数学方法可以得到给定数字的中位数及其出现频率。

和

Answer 1

您可以开始按顺序对频率求和，当总和超过总数的一半时，您会找到中位数。

counts = {1: 5, 2: 4, 3: 8}
total = sum(counts.values())
s = 0
for k in sorted(counts.keys()):
  s += counts[k]
  if s > total / 2:
    break
print 'median:', k