蓄水池采样算法
最新回答
听风入韵
2026-10-18 12:34:39
蓄水池算法（Reservoir Sampling）是解决这类问题的有效方法。
假设需要采样的数量为n。
证明过程：当走到第k步时，被k个元素替换的概率等于第k个元素被选中的概率乘以k个元素被选中替换的概率，即1/n。那么，不被第k个元素替换的概率为1-1/n。依次类推，不被k个元素替换的概率为(1-1/n)^(k-1)。
当递推到第n个元素时，第k个元素被保留的概率等于被选中的概率乘以不被替换的概率，即1/n * (1-1/n)^(n-1)。
对于第k个元素，其在第k步被选中的概率为1/n，不被k个元素替换的概率为(1-1/n)^(k-1)，当递推到第n个元素时，被保留的概率等于被选中的概率乘以不被替换的概率，即1/n * (1-1/n)^(n-1)。
因此，对于每个元素，被保留的概率都是1/n。
简单理解：遍历长度为n的数组。当第i次遇到target的元素时，随机选择区间[0, n)内的一个整数，如果其等于0，则将返回值置为该元素的下标，否则返回值不变。
设nums中有m个值为target的元素，该算法会保证这m个元素的下标最终返回值概率均为1/n，证明如下。
P(第i次遇到值为target的元素下标成为最终返回值) = P(第i次随机选择的值=0) x P(第i+1次随机选择的值!=0) x ... x P(第k次随机选择的值!=0)
相关代码说明参考蓄水池采样算法（Reservoir Sampling）原理，证明和代码。
热门标签
