2568-最小无法得到的或值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

如果存在一些整数满足 0 <= index1 < index2 < ... < indexk < nums.length ，得到
nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我们说 x 是 可表达的
。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

提示 1

暴力做法是从小到大枚举答案，但这显然会超时。

如何利用「x 不是答案」这一信息呢？

提示 2

如果 1 不是答案，说明 1 在 nums 中，因为 1 只有一个比特是 1（下同）。

继续枚举，如果 2 不是答案，说明 2 在 nums 中。

那么 3 肯定不是答案，因为 1 和 2 都在 nums 中，且 1|2=3。

继续枚举，如果 4 不是答案，说明 4 在 nums 中。

那么 5,6,7 肯定不是答案，因为 1,2,4 都在 nums 中，它们可以通过或运算组成 1 到 7 中的任意数字。

提示 3

因此，我们只需要从小到大挨个判断 2^i 是否在 nums 中，第一个不在 nums 中的就是答案。

代码实现时，可以用哈希表可以加速这个判断过程。

附：视频讲解 。

[sol1-Python3]
1
2
3
4
class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        s = set(nums)
        return next(1 << i for i in count() if 1 << i not in s)
[sol1-Java]
1
2
3
4
5
6
7
8
9
class Solution {
    public int minImpossibleOR(int[] nums) {
        var s = new HashSet<Integer>();
        for (int x : nums) s.add(x);
        for (int i = 1; ; i <<= 1)
            if (!s.contains(i))
                return i;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minImpossibleOR(vector<int> &nums) {
        unordered_set s(nums.begin(), nums.end());
        for (int i = 1;; i <<= 1)
            if (!s.count(i))
                return i;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
func minImpossibleOR(a []int) (ans int) {
	has := map[int]bool{}
	for _, v := range a {
		has[v] = true
	}
	for i := 1; ; i <<= 1 {
		if !has[i] {
			return i
		}
	}
}

复杂度分析

  • 时间复杂度：O(n+\log U)，其中 n 为 nums 的长度，U=\max(\textit{nums})。
  • 空间复杂度：O(n)。

进一步优化

由于只需要看 2 的幂次，我们可以用一个 mask 记录 nums 中是 2 的幂次的数。

那么答案就是 mask 中的最低比特 0。这可以取反后，用 lowbit 得到，具体见 视频讲解 。

[sol2-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def minImpossibleOR(self, nums: List[int]) -> int:
        mask = 0
        for x in nums:
            if (x & (x - 1)) == 0:  # x 是 2 的幂次
                mask |= x
        mask = ~mask
        return mask & -mask  # lowbit
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minImpossibleOR(int[] nums) {
        int mask = 0;
        for (int x : nums)
            if ((x & (x - 1)) == 0) // x 是 2 的幂次
                mask |= x;
        mask = ~mask;
        return mask & -mask; // lowbit
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minImpossibleOR(vector<int> &nums) {
        int mask = 0;
        for (int x : nums)
            if ((x & (x - 1)) == 0) // x 是 2 的幂次
                mask |= x;
        mask = ~mask;
        return mask & -mask; // lowbit
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
func minImpossibleOR(nums []int) int {
	mask := 0
	for _, x := range nums {
		if x&(x-1) == 0 { // x 是 2 的幂次
			mask |= x
		}
	}
	mask = ^mask
	return mask & -mask // lowbit
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 的长度。
  • 空间复杂度：O(1)。仅用到若干额外变量。

可以用到这个优化技巧的题目

如果你觉得自己的思维能力有些薄弱，可以做做 从周赛中学算法 - 2022 年周赛题目总结（下篇） 中的「思维题」这节，所有题目我都写了题解。

 Comments
On this page
2568-最小无法得到的或值
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 复杂度分析
  5. 进一步优化
  6. 复杂度分析
  7. 可以用到这个优化技巧的题目