最小无法得到的或值
难度:
标签:
题目描述
You are given a 0-indexed integer array nums.
We say that an integer x is expressible from nums if there exist some integers 0 <= index1 < index2 < ... < indexk < nums.length for which nums[index1] | nums[index2] | ... | nums[indexk] = x. In other words, an integer is expressible if it can be written as the bitwise OR of some subsequence of nums.
Return the minimum positive non-zero integer that is not expressible from nums.
Example 1:
Input: nums = [2,1] Output: 4 Explanation: 1 and 2 are already present in the array. We know that 3 is expressible, since nums[0] | nums[1] = 2 | 1 = 3. Since 4 is not expressible, we return 4.
Example 2:
Input: nums = [5,3,2] Output: 1 Explanation: We can show that 1 is the smallest number that is not expressible.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
代码结果
运行时间: 43 ms, 内存: 28.3 MB
/*
题目思路：
1. 使用Java Stream API实现与上述Java代码相同的逻辑。
2. 使用Stream来处理数组元素和HashSet。
3. 使用集合操作来更新和检查可表达的数字。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public int findSmallestNonExpressible(int[] nums) {
Set<Integer> expressibleNumbers = new HashSet<>();
expressibleNumbers.add(0);
for (int num : nums) {
Set<Integer> newExpressible = expressibleNumbers.stream()
.flatMap(existing -> IntStream.of(existing, existing | num).boxed())
.collect(Collectors.toSet());
expressibleNumbers = newExpressible;
}
int smallestNonExpressible = 1;
while (expressibleNumbers.contains(smallestNonExpressible)) {
smallestNonExpressible++;
}
return smallestNonExpressible;
}
}解释
方法:
该题解采用了位运算的方法来寻找最小无法得到的或值。首先，它检查数组中的每个数是否是2的幂（即只有一个位是1），这是通过判断x & (x - 1) == 0来实现的，因为只有2的幂和零才能满足这一点。随后，将这些2的幂通过或运算累积到mask变量中。最后，通过取mask的补码，并与其补码的相反数进行与运算，得到最低位的1，这个最低位的1代表的就是最小的无法通过给定数组的子序列得到的非零整数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到检查每个数是否是2的幂，那么在数组中存在非2的幂的数时，这些数对寻找最小无法得到的或值有何影响？
▷🦆
为什么题解中只考虑2的幂，对于组合多个数的或运算结果会怎样影响寻找最小无法得到的或值？
▷🦆
题解中使用了`mask = ~mask`来找出未出现的2的幂，这种方法是否能确保找到所有未通过数组子序列得到的非零整数中的最小值？
▷