algorithm - 给定一个数组作为输入，找到具有每个子数组中值的输出数组，其索引从 0 到 i(i = 1,2...array.length-1)

Question

给定一个数组作为输入，找到输出数组，该数组具有索引从 0 到 i(i = 1,2...array.length-1) 的每个子数组的中值。

所以基本上给定数组A[]，输出数组B[]。 B[i] 是 A[0] ... A[i] 的中位数。

我正在考虑用动态规划来存储每个子数组中位数前后的两个数。但它不知何故变得复杂。有没有更简单的解决方案？

Answer 1

基本上，我们在这里需要的是一个支持两种操作的数据结构:添加一个任意元素和找到到目前为止添加到它的所有元素的中值。

1. 概念上最简单的解决方案是存储所有子树大小的平衡二叉搜索树(添加操作只是向树中添加一个元素，而找到中位数只是从树根开始的一次遍历(我们可以选择在每个节点中去哪里，因为我们知道所有子树的大小。但是这个实现起来可能有点乏味(标准库中的二叉搜索树通常不支持有效地“获取第 k 个元素”操作) .

2. 这是另一个使用两个堆的解决方案(也是 O(N log N))。它在实现方面更容易，因为标准库中的优先级队列工作正常。

   • 让我们维护两个堆:low(最大堆)和high(最小堆)。不变量是:low 的任何元素都小于或等于 high 的任何元素，并且它们的大小最多相差一个。

   • 最初，它们是空的。

   • 当我们添加一个新数字时，我们执行以下操作:如果它小于或等于 low 中的最大元素，我们添加到 low。否则，我们添加到 high。很容易看出第一个不变量成立。如何保持第二不变性？如果插入后它们的大小相差 2，我们可以从较大的堆中弹出顶部元素并插入到另一个堆中。现在它们的大小最多相差一个。因此，当我们添加一个新元素时，我们可以在 O(log N) 时间内恢复这两个不变量。

   • 这两个不变量意味着以下属性:如果 size(low) != size(high)，则中位数是较大堆的顶部元素。如果它们的大小相等，则中位数是其中一个的顶部(究竟是哪个？这取决于具有偶数个元素的数组的中位数的定义)。