如何有效地找到数组的所有子数组的中位数？

Question

我一直在尝试解决这个问题，但我没有想出有效的方法。有人可以帮我解决这个问题吗？

问题定义可以在以下位置找到： https://www.hackerrank.com/contests/daiict-summer-long-2022/challenges/median-20-1

我试图从排序的角度思考，然后是中值的频率计数，但这会扰乱原始子数组结构，从而改变中值。所以我至少需要花费 O(N²logN) 时间，这太慢了！

可能这个问题可能很标准，我找不到参考。我尽力找到任何类似的问题或一些我没有遇到过的开箱即用的技术。

Answer 1

这可以及时解决

O(n log(n))

。我会让你开始。

关键是找到一种方法，给定

x

，计算有多少中间值低于、等于或高于

x

。您不想找到它们是什么，只需数数即可。

为此，您需要进行大量跟踪。

by whether the interval is odd/even in length
    by whether the median is below/at/above the wanted
        by whether the median is in the interval
            queue of count of open intervals with median `i` away
            total in queue
            total counted so far

但是重点是，这是固定数量的数据。对于我们看到的数组的每个元素，我们可以及时更新每个元素

O(1)

。 （你必须让逻辑恰到好处。）所以总时间是

O(n)

一次性完成。

有了这件作品，我们可以做以下事情。

1. 对值进行排序
2. 对中位数 mid 进行二分查找

注意，我假设值是不同的。如果不是，我们可以稍微调整一下，使它们不同，找到答案，然后撤消调整得到答案。

在 Python 中，调整就像将

value

替换为

adjusted_value = (value, position_in_array)

一样简单。倒数是

value = adjusted_value[0]

.