如何在O(1)时间复杂度下跟踪动态键值集合的中位数？

核心思路 #

利用题目允许「外部参数可任意时间复杂度计算」的条件，把中位数的计算逻辑移到外部执行，内部仅负责维护键值映射和跟踪中位数，确保set/remove操作严格满足O(1)时间要求。

内部维护的状态 #

• key_values: 字典，存储键K到对应数值V的映射，仅用于记录当前存在的键值对
• current_median: 变量，存储当前跟踪的中位数数值

操作实现 #

1. set(K, V, new_median) 操作

• 功能：设置键K的值为V，并更新中位数为外部计算好的new_median
• 代码实现：

def set(self, K, V, new_median):
    self.key_values[K] = V
    self.current_median = new_median

• 外部调用前需完成的计算：
  • 如果是更新操作，先从当前key_values中移除K的旧值
  • 将新值V加入后得到完整的有序值列表
  • 计算新的中位数new_median，作为参数传入

2. remove(K, new_median) 操作

• 功能：删除键K，并更新中位数为外部计算好的new_median
• 代码实现：

def remove(self, K, new_median):
    del self.key_values[K]
    self.current_median = new_median

• 外部调用前需完成的计算：
  • 从当前key_values中移除K对应的旧值
  • 得到新的有序值列表，计算新的中位数new_median，作为参数传入

为什么这是无bug的？ #

• 内部逻辑极简，仅做哈希表操作和变量赋值，完全避免了复杂的索引维护、堆调整等容易出错的逻辑
• 中位数的计算完全由外部完成，外部可通过排序、遍历等方式准确计算，确保结果正确
• 严格满足set/remove操作O(1)的时间要求，所有复杂计算都放在外部，不占用内部操作的时间

关于传入排序索引的替代方案说明 #

如果坚持要传入排序索引而非直接传入中位数，会遇到致命问题：插入/删除元素时，其他元素的索引会发生偏移，导致内部维护的索引映射需要批量更新，无法做到O(1)操作。除非外部能保证所有元素的索引是静态不变的（比如基于数值的唯一秩，而非插入位置），但这种情况下仍需要外部计算中位数对应的秩，最终还是回到「外部计算中位数」的思路，因此不推荐此方案。

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