Meta 最大元素下标随机选择：水塘抽样与均匀性证明

题意与假设

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

• 返回最大元素出现的下标，空输入返回None；重复数值对应不同位置。
• 随机源保证对每个bound独立均匀。训练数值可比较，排除NaN或需另行定义其排序。

解题路线

1. 遇到更大值时重置best与count=1，选它的下标。遇到相等最大值时count++，以1/count概率替换当前选择。遇到更小值不改变状态。
2. 归纳证明：第k个最大值被选概率1/k；此前任一个的原概率1/(k−1)乘本轮不替换概率(k−1)/k，仍为1/k。
3. 无须先存全部最大值位置；双遍扫描也可先数最大值再抽第几个出现，但流式输入可能无法二次读取。水塘法单遍且不会存O(numberOfTies)列表。

手动走一遍

[2,7,7,1,7]，下标1/2/4各概率1/3。第三个7到来时以1/3替换；此前每个位置概率1/2再乘2/3，也为1/3。

Python 参考实现

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

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

from random import randrange


def random_maximum_index(values, randbelow=randrange):
    """Uniform among maximum-valued positions, using O(1) auxiliary storage."""
    best = None
    count = 0
    selected = None
    for index, value in enumerate(values):
        if best is None or value > best:
            best, count, selected = value, 1, index
        elif value == best:
            count += 1
            if randbelow(count) == 0:
                selected = index
    return selected

复杂度

O(n)时间、O(1)辅助空间；n次读取是必要，因为最后一项可能最大。

易错点与追问

容易失分的边界

• 每遇到tie以固定1/2替换会偏向后来的最大值。
• count未在更大值时重置，会把已不属于最终最大值的元素算入概率。

继续深挖

• 独立测试可以穷举所有随机分支并按各分支概率相乘，精确核对下标分布，避免频率测试偶然失败。
• 若要均匀返回k个最大值位置，扩展为容量k的水塘并定义不足k时返回所有位置。