algorithm - 寻找中位数

Question

可能重复：
有效地找到数组中元素的等级？

如果我有一个元素数组 A [0 到 15]，并且我知道中位数在 A [8..11] 范围内。如何通过从 A[8..11] 中选择 A 中所有元素的中位数来找到它？它的等级会是多少？我已经阅读了很多关于此的内容，但我找不到这个特定问题的答案。任何帮助表示赞赏。该数组基本上包含二维点，我想将这些点分成矩形区域。

Answer 1

您不能仅通过观察这些元素的子集来知道一组元素的中位数。中位数取决于整个集合的每个元素。

Answer 2

我不认为你可以。中位数是排序时将数据一分为二的数据元素。

如果它已排序，那通常是 data[0..15] 数组的 data[7] 和 data[8] 的平均值。

如果它没有排序，那么如果不检查所有元素就无法找到它。

Answer 3

如果要将数组拆分为两组“小”和“大”值，最简单的方法是对数组进行排序。如果您不想对整个数组进行排序，则可以使用修改后的快速排序：对数组进行分区后，只对包含中位数的一半数组进行排序（除非分区结果是中位数，在在这种情况下你可以停止）。