如何设计O(1)复杂度、正确率≥3/4的概率算法判断二进制数组是否含1

核心方法是固定次数的随机采样，全程仅做常数次数组访问，满足O(1)时间复杂度要求，具体推导和实现逻辑如下：

• 首先明确两种情况的特征：如果数组存在1，那么1的数量至少是ceil(n/2)，占比不低于1/2，也就是说从数组里随机抽一个元素，抽到0的概率最高为1/2。
• 单次采样的错误场景：数组实际有1，但刚好抽到了0，错误概率≤1/2，不满足≤1/4的要求，我们可以通过多次独立采样降低错误概率。
• 两次独立采样的错误率计算：数组有1的前提下，连续两次都抽到0的概率≤(1/2) * (1/2) = 1/4，刚好符合错误率要求。

具体算法实现 #

1. 独立随机生成两个取值范围在[0, n-1]的数组下标（允许重复）
2. 依次读取两个下标对应的元素：
   • 只要任意一个元素为1，直接判定数组包含1，该结果100%正确
   • 如果两个元素都为0，判定数组全为0，该结果错误概率≤1/4

正确性验证：仅当数组实际包含1、且两次采样都刚好抽到占比不超过1/2的0时才会判断错误，该场景发生概率最高为1/4，完全符合题目要求。

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