主页 / 问题 / 1252212
Accepted
Sergei Zhilinski
Asked:2022-03-06 05:33:22 +0800 CST2022-03-06 05:33:22 +0800 CST

构造kd树时计算中位数

  • 772

我不明白中位数是如何计算的。我分析一项任务，我有以下数据集：(3; 4); (6; 1); (6; 6); (9; 7); (11; 2); (13; 6); (15; 1)。

由此有必要建立一个kd树。我正确构建，但并非所有中位数都同意答案。这是屏幕截图中的正确答案：

kd树

我的问题是什么：我计算中位数1：我将X的所有值相加，除以7。同样的方法得到9。我计算中位数2：我从(3; 4)求和Y；(6; 1); (6; 6) 除以 3。 (1+6+4)/3 = 3.66。我数中位数 3：我得到 4，等等。那些。很明显，解中考虑了中位数，对元素进行了划分，然后中位数从右侧向最小值移动。为什么？不应该使用通常的中位数吗？

деревья

1 个回答

  1. Best Answer

    您混淆了中位数和均值。

    中位数是集合中的这样一个值，即有相等相等的元素小于它和大于它。如果集合已排序，则中位数将位于中间位置 - 它将有一个索引n/2
    （对于奇数，这个位置是唯一确定的，对于偶数，中间一对被认为是中位数）

    例如，对于一个集合，中1,1,3,4,5,6,29位数为 4，平均值为 7。

    在第一次拆分之后，您剩下(3; 4); (6; 1); (6; 6);Y 集合1,4,6中位数 4，(9; 7); (11; 2); (13; 6); (15; 1)Y 集合1,2,6,7和中位数 6 作为排序顺序索引 2 处的元素。

    PS 求中位数，不需要全排序，有更快的方法（Quickselect）

    • 2

相关问题