压缩排序数组中位数：按频数跨越目标秩

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每数组为(value,count)的非降值run，count为正整数；value按本文代码为整数。
• 数组可空但总元素数>0。偶数中位数取两中值的精确有理均值，避免浮点溢出/舍入。

解题路线

1. 汇总各值频数，求总count N，中间0基秩为(N−1)//2及N//2。排序值桶后累积count，找到两秩落在哪个桶。
2. 本代码是易验证汇总排序基线；输入run本来有序时，双流/多流归并可不另排序并只扫到中位数，内存与复杂度进一步优化。
3. 同一值可在不同run多次出现，先加计数；计数算术可能大，使用任意精度或明确溢出约束。返回Fraction不复制重复元素。

手动走一遍

[(1,1000000),(5,2)]与[(3,1)]合计1000003，中位仍1，只处理3个run。[1×1,4×1]中位=(1+4)/2=5/2；两个目标同桶要让值贡献两次。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def median_rle(*arrays):
    counts={}
    for array in arrays:
        last=None
        for value,count in array:
            if type(count) is not int or count<=0 or last is not None and value<last:
                raise ValueError("sorted values and positive run counts required")
            counts[value]=counts.get(value,0)+count;last=value
    total=sum(counts.values())
    if not total:raise ValueError("empty median")
    targets=((total-1)//2,total//2);found=[];prefix=0
    for value in sorted(counts):
        end=prefix+counts[value]
        for rank in targets:
            if prefix<=rank<end:found.append(value)
        prefix=end
    from fractions import Fraction
    return Fraction(sum(found),2)

复杂度

r输入run、d不同值，基线O(r+dlogd)时间、O(d)空间；双已排序流归并可O(r)时间/O(1)除迭代器空间。不是O(总展开长度)。

易错点与追问

容易失分的边界

• 偶数时只找第N//2个数会返回上中位而非平均。
• run count0/负数会破坏秩扫描，应拒绝或预规范化。

继续深挖

• 计数能否外部流读取并在已知总N时只扫前半？
• 要按统计学其他分位定义，如何处理秩插值？