class Solution {
public:
int minImpossibleOR(vector<int>& nums) {
}
};
2568. 最小无法得到的或值
给你一个下标从 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 <= 1051 <= nums[i] <= 109原站题解
python3 解法, 执行用时: 72 ms, 内存消耗: 24.1 MB, 提交时间: 2023-02-20 23:11:55
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
java 解法, 执行用时: 1 ms, 内存消耗: 56.8 MB, 提交时间: 2023-02-20 23:11:44
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
}
}
cpp 解法, 执行用时: 80 ms, 内存消耗: 46.3 MB, 提交时间: 2023-02-20 23:11:32
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
}
};
golang 解法, 执行用时: 68 ms, 内存消耗: 9.4 MB, 提交时间: 2023-02-20 23:11:12
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
}
golang 解法, 执行用时: 80 ms, 内存消耗: 9.6 MB, 提交时间: 2023-02-20 23:10:58
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
}
}
}
cpp 解法, 执行用时: 176 ms, 内存消耗: 66.4 MB, 提交时间: 2023-02-20 23:10:44
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;
}
};
java 解法, 执行用时: 24 ms, 内存消耗: 53.1 MB, 提交时间: 2023-02-20 23:10:31
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;
}
}
python3 解法, 执行用时: 64 ms, 内存消耗: 30.8 MB, 提交时间: 2023-02-20 23:10:15
class Solution:
def minImpossibleOR(self, nums: List[int]) -> int:
s = set(nums)
return next(1 << i for i in range(32) if 1 << i not in s)