如何高效查找数据流中元素的排名？特定条件下求数据流中位数的实现疑问

算力阿峰

2026-5-21

问题1：如何高效查找数字数据流中某个元素的排名？

首先得明确「排名」的定义——通常有两种：一种是小于等于该元素的元素总数，另一种是严格小于该元素的个数加1。不同场景下的最优解法不一样，我分两种情况给你拆解：

离线场景（所有数据提前已知）

如果数据流是静态的、所有元素都能提前获取，这两种方法最实用：

排序+二分查找：先把所有元素排序存入数组arr。要查元素x的排名（小于等于x的总数），直接用upper_bound(arr.begin(), arr.end(), x) - arr.begin()；如果是严格小于x的个数加1，就用lower_bound(arr.begin(), arr.end(), x) - arr.begin() + 1。排序仅需一次O(nlogn)操作，每次查询都是O(logn)，简单高效。
离散化+树状数组/线段树：如果需要多次查询不同元素的排名，或者元素重复率高，先把所有元素离散化（将大值域映射到连续小索引），再用树状数组统计前缀和。遍历数组时，每遇到一个元素就给对应离散化索引的位置+1，查询x的排名就是查离散化后x的前缀和。时间复杂度O(nlogM)（M是不同元素的数量），适合大规模数据的多查询场景。

如果元素是实时流入的，无法提前获取所有数据，得用支持动态插入和统计的数据结构：

动态开点线段树：因为元素值域大（|a_i|≤2^{30），没法直接建数组，所以用动态开点的方式，每个节点存对应区间内的元素个数。插入元素时更新路径上的节点计数，查询排名时统计所有小于x的区间的计数总和。每次插入和查询都是O(log(2}30))≈O(30)，效率极高。
带大小统计的平衡二叉树：比如每个节点维护子树的节点数量，插入时更新路径上的节点大小，查询时根据左子树的大小判断当前元素的排名。C++里没有原生的这种结构，但可以用policy-based data structures里的ordered_set（处理重复元素的话，需要把元素和唯一索引配对），或者自己实现红黑树并维护子树大小。
分块法：把元素分成多个大小为√n左右的有序块。插入时找到对应的块，用二分法插入保持块内有序（O(√n)时间）；查询时遍历所有块，统计每个块内小于x的元素个数并累加（O(√n)时间）。实现简单，适合对时间要求不是极致苛刻的场景。

问题2：3-pass算法求数字数据流的中位数（空间O(√n)）

你的场景是输入重复3次的奇数n和n个整数，要求用3-pass算法，时间O(nlogn)，空间O(√n)。我给你梳理具体的实现思路和优化点：

首先选分块大小B=√n（比如n=1e7时，B≈3162），这样每个块的元素数量是O(√n)，刚好符合空间限制：

第一次遍历输入的n个元素，找到全局的最小值min_val和最大值max_val（用64位整数存，避免溢出）。
把[min_val, max_val]分成B个等长区间，每个区间的长度是(max_val - min_val)/B + 1（加1是为了覆盖所有元素）。
维护一个大小为B的计数数组，再次遍历n个元素，统计每个区间内的元素数量。
累加计数数组的元素，找到第一个累加和超过(n+1)/2的区间（因为n是奇数，中位数是第(n+1)/2个元素），这个区间就是中位数所在的目标块，记为[L, R)。

遍历n个元素，把所有属于[L, R)的元素收集到一个数组里，然后对这个数组排序。这个数组的大小最多是n/B=O(√n)，完全符合空间要求，排序的时间是O(√n log√n)=O(√n logn)，相对于O(n)的遍历时间可以忽略。

再次遍历n个元素，统计有多少元素小于L，记为cnt_less。中位数就是排序后的目标块数组中第(n+1)/2 - cnt_less - 1个元素（因为数组是0索引的）。

因为你的输入是完全重复3次的相同数据，所以只需要对第一次输入执行上述3-pass流程，得到中位数后，后面两次输入直接输出这个结果就行，不用重复处理三次数据流——这样能节省大量时间，毕竟3*1e7=3e7个元素的遍历开销不小。

n最大到1e7，三次就是3e7个元素，必须用高效的输入方法。你代码里的io.h和next_token应该是自定义的快速读入实现（比如用getchar()批量读取），这是对的，别用默认的cin（太慢）。如果是自己实现快速读入，要注意处理负数和多组输入的边界情况。

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