问询：设计支持logn插入与O(1)查询的子线性空间在线中位数方案

嘿，这个问题问到点子上了——咱们先解决第一个核心需求：设计满足插入O(logn)、中位数查询O(1)的结构，再聊聊子线性空间的可能性。

一、满足插入O(logn)、查询O(1)的经典实现：双堆结构 #

这是业界最常用的方案，核心思路是用两个堆把元素分成两部分：

• 一个最大堆（max-heap）：存储当前所有元素中较小的一半，堆顶是这一半的最大值
• 一个最小堆（min-heap）：存储当前所有元素中较大的一半，堆顶是这一半的最小值

维护规则 #

• 最大堆的元素数量要么和最小堆相等，要么比最小堆多1（这样能保证奇数个元素时，最大堆顶就是中位数；偶数个时，两个堆顶的平均值就是中位数）
• 插入元素时的步骤：
  1. 如果元素小于等于最大堆顶，插入最大堆；否则插入最小堆
  2. 检查两个堆的大小差：如果最大堆比最小堆大2，就把最大堆的堆顶移到最小堆；如果最小堆比最大堆大1，就把最小堆的堆顶移到最大堆

时间复杂度验证 #

• 插入操作：堆的插入/弹出操作都是O(logk)（k为堆的当前大小），整体复杂度为O(logn)
• 中位数查询：直接取最大堆顶（奇数元素场景）或两个堆顶的平均值（偶数元素场景），完全是O(1)

举个简单的伪代码示例（Python风格，利用负数模拟最大堆）：

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []  # 存负数实现最大堆逻辑
        self.min_heap = []

    def add_num(self, num):
        # 先将元素插入对应堆
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        
        # 平衡两个堆的大小
        if len(self.max_heap) > len(self.min_heap) + 1:
            val = -heapq.heappop(self.max_heap)
            heapq.heappush(self.min_heap, val)
        elif len(self.min_heap) > len(self.max_heap):
            val = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -val)

    def find_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

二、子线性空间的实现可能性？ #

这里要分两种场景讨论：

1. 要求准确的中位数：不存在子线性空间方案 #

原因很直接：中位数的定义严格依赖所有元素的排序位置。如果用子线性空间，意味着无法存储全部元素，必然会丢失关键信息——比如你丢弃的某个元素恰好是中位数，或者它的存在会改变中间位置的元素，这就导致无法计算出准确的中位数。

换句话说，要得到准确的中位数，必须保留所有元素的完整排序相关信息，这必然需要O(n)的空间，无法做到子线性。

2. 允许近似的中位数：存在多种子线性空间方案 #

如果业务场景可以接受一定误差范围的近似中位数，那么有很多流式算法可以实现子线性空间：

• Greenwald-Khanna算法：通过维护有序的“摘要”列表记录元素位置范围，空间复杂度为O(log²n)，插入时间O(logn)，可在任意指定误差范围内返回近似中位数
• t-digest：基于分位数草图的算法，空间复杂度为O(logn)（精度越高，空间占用略增），适合处理大规模流式数据，能高效计算近似分位数（包括中位数）
• Reservoir Sampling：如果对精度要求不高，用蓄水池抽样可以在O(1)空间内维护样本，随机抽取近似中位数，误差相对较大但实现简单

这些算法的核心都是通过牺牲部分精度，用统计摘要替代完整元素存储，从而实现子线性空间占用。

内容的提问来源于stack exchange，提问作者H. Moshe