寻找数组所有子序列按位OR结果中缺失的最小整数（优化解法）

问题背景 #

给定数组（如arr = {1,3,4,0}），需找出所有子序列按位OR结果去重后集合中缺失的最小整数。直接生成所有子序列显然不可行（数组长度可达10^{5，子序列数量为2}10^5），必须用基于按位OR性质的优化方法。

核心思路 #

按位OR运算有一个关键性质：新元素加入后，新增的OR结果只能是原有结果与新元素的OR，或新元素本身。且由于元素最大值为10^5（二进制约17位），每一步维护的OR结果集合大小最多为17，时间复杂度可控制在O(n*logM)（n为数组长度，M为元素最大值），完全适配大规模数组。

具体步骤 #

1. 维护OR结果集合：初始化集合包含空序列的OR结果0，遍历数组中每个元素：
   • 临时生成新集合，包含当前元素，以及现有集合中所有元素与当前元素的OR结果
   • 将临时集合合并到主集合中去重
2. 查找缺失的最小整数：从0开始依次检查，第一个不在OR结果集合中的数即为答案。

代码实现（Python） #

def find_missing_min(arr):
    or_results = {0}
    for num in arr:
        # 生成当前元素带来的新OR结果
        new_ors = {val | num for val in or_results}
        new_ors.add(num)
        # 合并到结果集合
        or_results.update(new_ors)
    # 寻找缺失的最小整数
    res = 0
    while res in or_results:
        res += 1
    return res

# 测试示例
arr = [1, 3, 4, 0]
print(find_missing_min(arr))  # 输出2

复杂度说明 #

• 时间复杂度：O(n*logM)，n为数组长度，logM是元素最大值的二进制位数（约17），10^{5规模的数组总操作仅约1.7×10}6次，效率极高
• 空间复杂度：O(logM)，维护的OR结果集合大小最多为二进制位数，占用极小内存

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