求分步生成均匀随机分布的高效算法（时间复杂度<O(n)）

核心思路 #

利用数组索引的有序性，通过对数级步骤逐步缩小候选索引范围，每一步严格保证剩余候选元素的选中概率均匀，时间复杂度为O(log n)，远低于O(n)。

具体步骤 #

假设数组长度为n，初始候选索引范围是[0, n-1]：

• 初始化：设置当前候选区间左边界left = 0，右边界right = n-1。
• 迭代缩小范围：
  当left < right时：
  1. 计算区间中点mid = (left + right) // 2（向下取整），将区间拆分为左半部分[left, mid]和右半部分[mid+1, right]。
  2. 生成0到1的均匀随机数：若随机数小于(mid - left + 1) / (right - left + 1)，则保留左半部分，更新right = mid；否则保留右半部分，更新left = mid + 1。
• 终止条件：当left == right时，该索引对应的元素即为均匀随机选中的结果。

均匀性证明 #

• 初始状态下每个元素选中概率为1/n。
• 每一步选择子区间时，子区间被选中的概率等于其元素数量占原区间的比例，子区间内每个元素的最终选中概率为(子区间元素占比) * (1/子区间长度) = 1/原区间长度，因此每一步后剩余元素的选中概率始终保持均匀。

你的原算法问题分析 #

你之前通过min/max随机缩放范围的方案，问题在于随机收缩比例是[0,1]的均匀分布，导致边界区域被保留的概率远高于中间区域，最终结果集中在初始范围两端。而本方案基于元素数量比例选择子区间，从根源上保证了概率均匀性。

伪代码示例 #

def uniform_random_select(arr):
    n = len(arr)
    left, right = 0, n - 1
    while left < right:
        mid = (left + right) // 2
        left_segment_ratio = (mid - left + 1) / (right - left + 1)
        if random.random() < left_segment_ratio:
            right = mid
        else:
            left = mid + 1
    return arr[left]

时间复杂度说明 #

每一步区间长度至少减半，迭代次数为O(log n)，完全满足小于O(n)的要求。

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