O(n)时间找缺失整数：为何筛选后count(0s)仍≥count(1s)？

问题背景 #

数组A包含0到n的所有整数，但缺失一个数。题目限制无法直接访问完整整数，仅能通过fetch the jth bit of A[i]操作获取数组元素的第j位二进制值，且该操作耗时恒定。要求在O(n)时间内找到缺失的整数。

常规的求和差或异或解法，因需要访问每个整数的所有二进制位，时间复杂度为O(n logn)，不符合要求。书中给出的O(n)解法核心逻辑是：

1. 初始0到n的完整序列中，最低有效位（LSB）的0的数量≥1的数量：若n为奇数，0和1数量相等；若n为偶数，0的数量比1多1。
2. 统计当前数组该位的0、1数量，通过失衡情况判断缺失数的对应位（比如0的数量少于应有的数量，说明缺失数该位为0）。
3. 筛选掉所有该位与缺失数不同的元素，缩小问题规模，重复上述过程直到确定完整的缺失数。

疑问点：初始序列满足count(0s)≥count(1s)，但每次筛选掉半数元素后，为何这个计数关系依然成立？这是该算法能持续缩小规模的核心前提。

核心原因分析 #

每次筛选后保留的子数组，对应的是原0~n序列中，所有与当前已确定的缺失数前缀位完全匹配的数，这个子集本质上等价于一段连续的整数区间（或可拆分为1-2段连续区间，但其二进制位的分布规律与连续区间一致），而连续整数区间的任意二进制位都天然满足count(0s)≥count(1s)的规律：

• 对于任意二进制位j，每2^{(j+1)个连续整数为一个周期，每个周期内该位为0和1的数各占2}j个，数量相等。
• 如果序列长度不是2^(j+1)的整数倍，最后一个不完整的周期里，该位为0的数会先出现，因此0的数量要么和1相等，要么比1多1。

举个具体例子：
原序列是0~5（n=5），筛选出最低位为0的数得到[0,2,4]，这个子序列的第1位（次低位）分布是0、1、0，0的数量为2，1的数量为1，满足0≥1；如果缺失的是2，筛选后的子数组是[0,4]，此时我们要分析的是“原子集[0,2,4]中缺失一个数后的下一位分布”——原子集本身满足0的数量≥1的数量，缺失一个数后，只需对比当前统计结果和原子集的预期计数，就能判断缺失数的该位，而后续筛选出的子序列依然遵循连续区间的位分布规律，循环往复即可确定完整的缺失数。

简言之，每次筛选后的子序列始终对应一段（或等价于一段）连续整数，其任意二进制位的0、1数量必然满足count(0s)≥count(1s)，这是连续整数二进制位的天然分布特性，也是算法能持续缩小规模的关键。

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