优质数对的数目
难度:
标签:
题目描述
代码结果
运行时间: 80 ms, 内存: 32.1 MB
/*
* 思路:
* 1. 使用流操作遍历数组中的每一个数对 (num1, num2)。
* 2. 计算 num1 OR num2 和 num1 AND num2 的结果,并计算二进制中 1 的个数。
* 3. 过滤掉不满足 k 条件的数对,并计数。
*/
import java.util.stream.IntStream;
public int countGoodPairsStream(int[] nums, int k) {
int n = nums.length;
return (int) IntStream.range(0, n).boxed()
.flatMap(i -> IntStream.range(i, n)
.filter(j -> Integer.bitCount(nums[i] | nums[j]) + Integer.bitCount(nums[i] & nums[j]) >= k)
.mapToObj(j -> new int[] {nums[i], nums[j]}))
.count();
}
解释
方法:
该题解的思路是首先对数组去重,然后统计每个数字的二进制表示中1的个数,用Counter来计数各个位数的数字出现的次数。之后,遍历Counter的每一对位数(i, j),如果两者之和大于等于k,则说明这两个位数的数字组合成的数对满足条件,应该将它们出现的次数相乘,并累加到结果中。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法实现中,为什么首先选择对数组进行去重操作?去重对最终结果的计算有何影响?
▷🦆
在题解中提到,遍历Counter的每一对位数(i, j)时,只有当i + j >= k时才计算数对。这是否意味着对于i + j < k的情况,这些位数的数对可以完全忽略不计?
▷🦆
算法中对Counter中的每一对(i, u)和(j, v)进行了遍历,这是否能确保统计的每一对数字都是独一无二的数对?如果(i, u)和(j, v)相同,这种情况在计算中如何处理?
▷