找出数组中的 K-or 值
难度:
标签:
题目描述
You are given an integer array nums, and an integer k. Let's introduce K-or operation by extending the standard bitwise OR. In K-or, a bit position in the result is set to 1 if at least k numbers in nums have a 1 in that position.
Return the K-or of nums.
Example 1:
Input: nums = [7,12,9,8,9,15], k = 4
Output: 9
Explanation:
Represent numbers in binary:
| Number | Bit 3 | Bit 2 | Bit 1 | Bit 0 |
|---|---|---|---|---|
| 7 | 0 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 |
| Result = 9 | 1 | 0 | 0 | 1 |
Bit 0 is set in 7, 9, 9, and 15. Bit 3 is set in 12, 9, 8, 9, and 15.
Only bits 0 and 3 qualify. The result is (1001)2 = 9.
Example 2:
Input: nums = [2,12,1,11,4,5], k = 6
Output: 0
Explanation: No bit appears as 1 in all six array numbers, as required for K-or with k = 6. Thus, the result is 0.
Example 3:
Input: nums = [10,8,5,9,11,6,8], k = 1
Output: 15
Explanation: Since k == 1, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15.
Constraints:
1 <= nums.length <= 500 <= nums[i] < 2311 <= k <= nums.length
代码结果
运行时间: 42 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 利用 Java Stream 对数组进行处理。
* 2. 对于每一位，我们通过 Stream 检查有多少数字的该位为 1。
* 3. 如果某一位上有至少 k 个 1，则将该位结果置为 1。
*/
import java.util.stream.IntStream;
public class KOrStream {
public static int findKOrValue(int[] nums, int k) {
int maxBits = IntStream.of(nums).map(num -> Integer.toBinaryString(num).length()).max().orElse(0);
int result = 0;
for (int i = 0; i < maxBits; i++) {
int bitIndex = i;
long count = IntStream.of(nums).filter(num -> (num & (1 << bitIndex)) != 0).count();
if (count >= k) {
result |= (1 << i);
}
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {7, 12, 9, 8, 9, 15};
int k1 = 4;
System.out.println(findKOrValue(nums1, k1)); // 输出：9
int[] nums2 = {2, 12, 1, 11, 4, 5};
int k2 = 6;
System.out.println(findKOrValue(nums2, k2)); // 输出：0
int[] nums3 = {10, 8, 5, 9, 11, 6, 8};
int k3 = 1;
System.out.println(findKOrValue(nums3, k3)); // 输出：15
}
}
解释
方法:
时间复杂度:
空间复杂度: