在线性时间的未排序数组中查找加权中位数

Question

这是来自coursera的算法课程中的实践问题;我被困了几个星期。

问题在于：＜code＞给定一个由n个不同的未排序元素x＜sub＞1＜/sub＞组成的数组，x＜sub＞2＜/sub＞，…，x＜sub＞n＜/次级＞ε，加权中值是一个元素x_k，对于该元素，值小于x_k的所有元素的总权重最多为（总权重）/2，值大于x_k的元素的总重量最多为（总重）/2。观察最多有两个加权值。演示如何在O（n）最坏时间内计算所有加权中值。

课程主要涵盖分治算法，所以我认为开始学习的关键是确定哪些算法可以用于这个问题。

所涉及的算法之一是< code>RSelect算法，其形式为< code>RSelect(array X，length n，order statistic i)，对于加权中值可以写成< code>RSelect(array X，weights W，length n，order statistic i)。我对这种方法的问题是，它假设我事先知道中值，这似乎不太可能。还有一个问题是，枢纽是随机统一选择的，如果不计算每个条目的每个权重，我认为这不太可能与权重一起工作。

接下来是DSelect算法，其中使用中位数方法可以在不随机化的情况下计算轴心，因此我们可以计算适当的中位数。这似乎是一种可行的方法，我遇到的问题是，它还假设我提前知道我要寻找的价值。

DSelect（数组A，长度n，顺序统计i）用于未加权数组

加权数组的 DSelect（数组 A、权重 W、长度 n、阶次统计 i）

我是不是想得太多了？假设我提前知道（总权重）/2的值，我应该使用DSelect吗？我想即使我计算它，它也只会为运行时间增加线性时间。但是，这与预先计算加权数组没有什么不同（将A， W组合成Q，其中qi=xi*wi）并将其转换回我可以使用RSelect的未加权数组问题（加上对有两个媒体的情况的一些考虑）

我找到了https://archive.org/details/lineartimealgori00blei/page/n3和https://blog.nelsonliu.me/2016/07/05/gsoc-week-6-efficient-calculation-of-weighted-medians/它们描述了这个问题，但它们的方法似乎没有在本课程中介绍（而且我不熟悉heaps/heapsort）

Answer 1

这个问题可以通过quickselect的一个简单变体来解决：

1. 计算所有权重的总和并除以 2 得到目标总和
2. 选择一个透视表并将数组分区为更大和更小的元素
3. 对较小分区中的权重求和，然后从总计中减去，得到另一个分区中的权重和
4. 返回到 2 以使用适当的目标总和处理适当的分区

与普通quickselect一样，如果使用（正常、未加权）中间值方法选择轴，在最坏的情况下，这将变为线性。

Answer 2

这种平均性能可以通过Quickselect实现。

可以用储层采样算法选择随机选择的枢轴(加权)。你是正确的，寻找第一个枢纽的时间是< code>O(n)，但是你正在处理的列表的大小将遵循一个几何级数，所以寻找枢纽的总成本将仍然计算出来只有< code>O(n)。