9

对于一个映射，其中键表示序列的数字，值表示该数字在序列中出现的频率，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。

4

4 回答 4

5

使用番石榴：

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，但最简单的方法通常很好。

于 2010-06-16T15:21:43.657 回答
5

线性时间

如果您知道数字的总数（在您的情况下为 16），您可以从地图的开头或结尾开始计算计数，直到您到达第（n/2）个元素，或者以防万一sum 是平均 floor(n/2)th 和 ceil(n/2)th 元素 =中位数。

如果您不知道总数，则必须至少检查一次。

次线性时间

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

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

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

这将使内存使用量翻倍，但中位数的性能为 O(log n)，total_count 的性能为 O(1)。

于 2010-06-16T12:21:23.683 回答
2
  • 使用 a SortedMap，即 aTreeMap
  • 遍历map一次，计算元素的总数，即所有出现的总和
  • 再次迭代并累加出现次数，直到达到总数的一半。导致总和超过总数一半的数字是中位数
  • 广泛测试非一错误
于 2010-06-16T11:59:31.397 回答
1

对于简单但可能效率不高的算法，我会这样做：

1. 将地图展开为列表。

实际上说：遍历地图并将键'value-times'添加到新列表中。最后对列表进行排序。

//...
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)。这取决于您需要的中位数类型。如果它只是样本中位数，那么结果要么是最中间的值（对于具有奇数个元素的列表），要么是两个中间值的平均值（对于具有偶数长度的列表）。请注意，列表需要排序！

（参考：样本中位数/维基百科）

好的，好的，即使克里斯没有提到效率，这里有一个想法如何在不扩展地图的情况下计算样本中位数（！）......

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;
  }
}

（我手头没有编译器——如果它有很多语法错误，请将其视为伪代码；））

于 2010-06-16T12:06:21.093 回答