Medium

题目描述

给你一个下标从 0 开始的整数数组 nums。

如果存在一些下标 0 <= index1 < index2 < ... < indexk < nums.length，使得 nums[index1] | nums[index2] | ... | nums[indexk] = x，那么我们说整数 x 可以从 nums 中表达出来。换句话说，如果一个整数可以写成 nums 某个子序列的按位或运算结果，那么它就是可表达的。

返回不能从 nums 中表达出来的最小正整数。

示例 1：

输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中。我们知道 3 是可表达的，因为 nums[0] | nums[1] = 2 | 1 = 3。由于 4 不可表达，我们返回 4。

示例 2：

输入：nums = [5,3,2]
输出：1
解释：我们可以证明 1 是不可表达的最小数字。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题的关键洞察是：答案一定是 2 的幂次。

为什么？考虑按位或运算的性质：

  • 按位或只能将某个位从 0 变为 1，不能从 1 变为 0
  • 如果我们想要构造一个数 x，那么 x 的每个为 1 的位都必须能从数组中的某个数获得
  • 对于 2 的幂次 2^k，它只有第 k 位为 1，其他位都为 0

因此，如果数组中不存在某个 2 的幂次 2^k，那么无论如何进行按位或运算，都无法得到 2^k。而任何大于 2^k 且包含第 k 位的数，都可以通过 2^k 与其他数的按位或得到。

算法步骤：

  1. 将数组转换为集合，便于快速查找
  2. 从 2^0 = 1 开始，依次检查每个 2 的幂次是否在数组中
  3. 返回第一个不在数组中的 2 的幂次

这种方法的时间复杂度很低，因为即使数组中的最大值是 10^9，我们最多也只需要检查 30 个 2 的幂次（2^30 > 10^9）。

代码实现

class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        for (int power = 0; power <= 30; power++) {
            int powerOf2 = 1 << power;
            if (numSet.find(powerOf2) == numSet.end()) {
                return powerOf2;
            }
        }
        
        return 1 << 31;
    }
};

class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        num_set = set(nums)
        
        power_of_2 = 1
        while power_of_2 in num_set:
            power_of_2 <<= 1
        
        return power_of_2

public class Solution {
    public int MinImpossibleOR(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        
        for (int power = 0; power <= 30; power++) {
            int powerOf2 = 1 << power;
            if (!numSet.Contains(powerOf2)) {
                return powerOf2;
            }
        }
        
        return 1 << 31;
    }
}

var minImpossibleOR = function(nums) {
    const numSet = new Set(nums);
    
    let powerOf2 = 1;
    while (numSet.has(powerOf2)) {
        powerOf2 <<= 1;
    }
    
    return powerOf2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + log C)，其中 n 是数组长度，C 是数组中的最大值。构建集合需要 O(n)，检查 2 的幂次最多需要 O(log C) 次
空间复杂度O(n)，用于存储集合