设计随机算法判断数组是否含1：要求75%成功率、O(1)时间复杂度

首先明确题目给定的约束：长度为n的数组仅存在两种互斥状态：

• 状态1：所有元素都为0，不存在1
• 状态2：恰好一半元素为0、另一半元素为1，存在1
  要求算法判定成功率不低于75%，时间复杂度为O(1)

算法具体步骤 #

• 从数组中独立随机抽取2个元素，支持两种抽取方式：
  1. 不放回抽取：随机选2个不同下标的元素
  2. 有放回抽取：允许两次抽取同一个下标的元素
• 若抽取的2个元素中存在至少1个值为1的元素，直接返回存在1
• 若抽取的2个元素全为0，返回全为0

正确率验证 #

算法仅会在数组为状态2（存在1）时出现误判，误判场景为两次抽取的元素恰好都是0：

1. 采用有放回抽取时：单次抽到0的概率为1/2，两次都抽到0的概率为 1/2 × 1/2 = 1/4，因此判定正确率为 1 - 1/4 = 75%，刚好满足要求
2. 采用不放回抽取时：误判概率为 C(n/2, 2) / C(n, 2) = (n-2)/(4(n-1))，该值永远小于1/4，正确率高于75%，同样满足要求
   数组为状态1（全为0）时，算法永远不会出现误判，因此整体正确率≥75%。

复杂度分析 #

算法仅执行固定2次元素读取和比较操作，和数组长度n完全无关，因此时间复杂度为O(1)，符合要求。

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