如何高效计算数组所有子数组的中位数？

核心思路 #

对于数组中的每个元素arr[i]，只需计算有多少个子数组以它为中位数，最后累加每个元素的计数即可。关键是避免暴力枚举所有子数组，转而通过差值统计+哈希表/树状数组优化时间复杂度。

具体实现步骤 #

1. 针对单个元素计算有效子数组数量
   以元素x = arr[i]为例，统计所有包含i的子数组中x是中位数的数量：

   • 定义差值diff = (子数组中大于x的元素数) - (子数组中小于x的元素数)
   • 若子数组为奇数长度，需满足：左边部分的diff1 + 右边部分的diff2 = 0。此时子数组中大于和小于x的元素数量相等，加上x自身，x就是中位数。
   • 若题目对偶数长度子数组的中位数有定义（比如取中间偏左/偏右元素），需对应调整差值条件（如diff1 + diff2 = 1或-1）。

2. 哈希表快速统计差值出现次数

   • 从i向左遍历，维护当前diff，用哈希表left_counts记录每个diff的出现次数（初始时diff=0，对应左边选0个元素的情况）。
   • 从i向右遍历，维护当前diff，每次查询left_counts[-diff]的数值，将其加到x的计数中（代表左边存在对应数量的组合，能和当前右边部分组成以x为中位数的子数组）。

3. 进阶O(NlogN)优化方案
   哈希表方法时间复杂度为O(N²)，大数据量下可通过**离线处理+树状数组（Fenwick Tree）**优化：

   • 将数组元素排序，依次处理每个元素作为中位数的情况。
   • 将数组转化为前缀差值数组，利用树状数组统计满足条件的前缀和出现次数，把时间复杂度降至O(NlogN)。

代码示例（哈希表版本） #

def count_median_frequency(arr):
    n = len(arr)
    freq = [0] * n
    for i in range(n):
        x = arr[i]
        left_counts = {0: 1}
        diff = 0
        # 遍历左侧元素
        for j in range(i-1, -1, -1):
            if arr[j] > x:
                diff += 1
            elif arr[j] < x:
                diff -= 1
            left_counts[diff] = left_counts.get(diff, 0) + 1
        # 遍历右侧元素并统计有效子数组
        diff = 0
        cnt = left_counts.get(-diff, 0)  # 仅包含当前元素的子数组
        for j in range(i+1, n):
            if arr[j] > x:
                diff += 1
            elif arr[j] < x:
                diff -= 1
            cnt += left_counts.get(-diff, 0)
        freq[i] = cnt
    # 汇总每个数值的出现频率
    value_freq = {}
    for num, cnt in zip(arr, freq):
        value_freq[num] = value_freq.get(num, 0) + cnt
    return value_freq

注意事项 #

• 若题目对偶数长度子数组的中位数定义特殊，需对应调整差值条件。
• 数组存在重复元素时，需统一等于x的元素的归类规则（比如归为大于或小于侧）。

内容的提问来源于stack exchange，提问作者RP_21