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

Question

这是coursera的一门算法类(class)中的练习题；我已经被困了几个星期了。

问题是这样的:
Given an array of n distinct unsorted elements x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub> ε X with positive weights w<sub>1</sub>, w<sub>2</sub>, ..., w<sub>n</sub> ε W, a weighted median is an element x<sub>k</sub> for which the total weight of all elements with values less than x<sub>k</sub> is at most (total weight)/2 and also the total weight of elements with values larger than x<sub>k</sub> is at most (total weight)/2. Observe that there are at most two weighted. Show how to compute all weighted medians in O(n) worst time


类(class)主要涵盖分而治之算法，因此我认为开始这门类(class)的关键是确定所涵盖的哪些算法可用于此问题。

涵盖的算法之一是 RSelect形式为 RSelect(array X, length n, order statistic i) 的算法对于加权中位数可以写成 RSelect(array X, weights W, length n, order statistic i) .我对这种方法的问题是它假设我提前知道中值，这似乎不太可能。还有一个问题是，枢轴是随机统一选择的，我认为如果不计算每个条目的每个权重，这不太可能适用于权重。

接下来是 DSelect算法，其中使用中位数的中位数方法可以在没有随机化的情况下计算主元，因此我们可以计算出适当的中位数。这似乎是可行的方法，但我遇到的问题是它还假设我提前知道我正在寻找的值。

DSelect(array A, length n, order statistic i)对于未加权的数组

DSelect(array A, weights W, length n, order statistic i)对于加权数组

我是不是想多了？我应该使用 DSelect 吗？假设我知道 (total weight) / 2 的值提前时间？我想即使我计算它也只会增加运行时间的线性时间。但这与预先计算加权数组 ( combine A, W into Q where q<sub>i</sub> = x<sub>i</sub>*w<sub>i</sub> ) 并将其转换回我可以使用 RSelect 的未加权数组问题没有什么不同。 (加上一些对有两个中位数的情况的解释)

我找到了 https://archive.org/details/lineartimealgori00blei/page/n3和 https://blog.nelsonliu.me/2016/07/05/gsoc-week-6-efficient-calculation-of-weighted-medians/描述了这个问题，但他们的方法似乎没有在类(class)中涵盖(而且我不熟悉堆/堆排序)

Answer 1

这个问题可以用一个简单的 quickselect 变体来解决:

1. 计算所有权重的总和除以2得到目标总和
2. 选择一个基准并将数组划分为更大和更小的元素
3. 将较小分区中的权重相加，并从总数中减去得到另一个分区中的总和
4. 回到2用合适的目标和处理合适的分区

就像普通的快速选择一样，如果您使用(普通的、未加权的)中位数方法来选择一个枢轴，那么在最坏的情况下这会变成线性的。