如何更快计算流动中位数？如何高效实现累计和过半索引查找？

我来帮你逐个拆解这两个问题的高效解法：

当然有！流动（滑动窗口）中位数的核心痛点是避免每次窗口滑动都重新排序整个窗口，这里有几种实用的高效方案：

• 双堆+延迟删除法：这是业界常用的经典思路。我们可以用两个堆来维护窗口内的元素：一个大顶堆存窗口左半部分（堆顶是左半最大元素），一个小顶堆存右半部分（堆顶是右半最小元素），保持两个堆的大小差不超过1。这样中位数要么是左堆堆顶，要么是两个堆顶的平均值。
  不过Python自带的heapq只支持小顶堆，所以大顶堆可以通过存储元素的负数来模拟。另外，窗口滑动时删除元素不能直接从堆里移除（heapq不支持高效删除），我们可以用一个哈希表记录待删除元素的计数，当堆顶元素是待删除项时，就弹出它并减少计数——这就是延迟删除的技巧。这种方法每次插入/删除的时间复杂度是O(logk)（k为窗口大小），取中位数是O(1)，非常适合大数据量的滑动窗口场景。

• 用优化后的第三方库：如果不想自己造轮子，直接用现成的库更省心。比如scipy.ndimage.median_filter，它是用C实现的，处理大数组时比纯Python代码快得多；还有pandas的rolling方法，比如df.rolling(window=k).median()，内部做了优化，处理结构化数据特别方便。

• numpy滑动窗口+中位数（适合小场景）：如果数据量不大，代码简洁性优先的话，可以用numpy.lib.stride_tricks.sliding_window_view生成所有滑动窗口，再用np.median计算每个窗口的中位数。不过这种方法本质上每个窗口都要排序，时间复杂度是O(nk logk)，窗口大的时候效率会明显下降，适合小窗口或小数据量的场景。

你的循环逻辑是对的，但Python循环在处理大数组时效率很低，用numpy的向量化操作能大幅提速，而且代码更简洁。这里有两种高效实现：

方法1：向量化累计和 + argmax #

先用np.cumsum计算累计和（这是向量化操作，比Python循环快几个数量级），再用np.argmax找到第一个满足累计和≥总和一半的索引：

import numpy as np

x = np.array([67, 51, 42, 37, 21, 10, 2, 2, 1, 1, 1])
total_half = x.sum() / 2
cumulative_sum = np.cumsum(x)
idx = np.argmax(cumulative_sum >= total_half)
print(idx)  # 输出1

np.argmax会返回布尔数组中第一个True的索引，正好符合我们找最小索引的需求。

方法2：searchsorted（超大数组首选） #

因为你的数组元素都是正数，累计和数组是严格递增的，所以可以用np.searchsorted实现O(logn)时间复杂度的查找，比np.argmax的O(n)更高效，尤其是数组长度达到百万级以上时：

import numpy as np

x = np.array([67, 51, 42, 37, 21, 10, 2, 2, 1, 1, 1])
total_half = x.sum() / 2
cumulative_sum = np.cumsum(x)
idx = np.searchsorted(cumulative_sum, total_half, side='left')
print(idx)  # 输出1

side='left'表示找到第一个大于等于total_half的元素位置，完全匹配我们需要的最小索引。

效率对比 #

举个例子，当数组长度是1e6时，向量化方法的运行时间大概是纯Python循环的1/100甚至更短，性能提升非常明显。

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