class Solution {
public:
long long countExcellentPairs(vector<int>& nums, int k) {
}
};
2354. 优质数对的数目
给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。
如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：
num1 和 num2 都 在数组 nums 中存在。num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。返回 不同 优质数对的数目。
如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2) 和 (2, 1) 不同。
注意：如果 num1 在数组中至少出现 一次 ，则满足 num1 == num2 的数对 (num1, num2) 也可以是优质数对。
示例 1：
输入：nums = [1,2,3,1], k = 3 输出：5 解释：有如下几个优质数对： - (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。 - (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。 - (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。 所以优质数对的数目是 5 。
示例 2：
输入：nums = [5,1,1], k = 10 输出：0 解释：该数组中不存在优质数对。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 60原站题解
golang 解法, 执行用时: 160 ms, 内存消耗: 10.4 MB, 提交时间: 2023-08-11 11:02:51
func countExcellentPairs(nums []int, k int) (ans int64) {
const U = 30
vis := map[int]bool{}
cnt := [U]int{}
for _, x := range nums {
if !vis[x] {
vis[x] = true
cnt[bits.OnesCount(uint(x))]++
}
}
s := 0
for i := k; i < U; i++ {
s += cnt[i]
}
for cx, ccx := range cnt {
ans += int64(ccx) * int64(s)
cy := k - 1 - cx
if 0 <= cy && cy < U {
s += cnt[cy]
}
}
return
}
golang 解法, 执行用时: 160 ms, 内存消耗: 11.2 MB, 提交时间: 2023-08-11 11:02:23
func countExcellentPairs(nums []int, k int) (ans int64) {
vis := map[int]bool{}
cnt := map[int]int{}
for _, x := range nums {
if !vis[x] {
vis[x] = true
cnt[bits.OnesCount(uint(x))]++
}
}
for cx, ccx := range cnt {
for cy, ccy := range cnt {
if cx+cy >= k { // (x,y) 是优质数对
ans += int64(ccx) * int64(ccy)
}
}
}
return
}
java 解法, 执行用时: 32 ms, 内存消耗: 56 MB, 提交时间: 2023-08-11 11:01:47
class Solution {
static final int U = 30;
public long countExcellentPairs(int[] nums, int k) {
var vis = new HashSet<Integer>();
var cnt = new int[U];
for (var x : nums)
if (vis.add(x)) ++cnt[Integer.bitCount(x)];
var ans = 0L;
var s = 0;
for (var i = k; i < U; ++i)
s += cnt[i];
for (var cx = 0; cx < U; ++cx) {
ans += (long) cnt[cx] * s;
var cy = k - 1 - cx;
if (0 <= cy && cy < U) s += cnt[cy];
}
return ans;
}
}
java 解法, 执行用时: 56 ms, 内存消耗: 57.8 MB, 提交时间: 2023-08-11 11:01:27
class Solution {
public long countExcellentPairs(int[] nums, int k) {
var vis = new HashSet<Integer>();
var cnt = new HashMap<Integer, Integer>();
for (var x : nums)
if (vis.add(x)) {
var c = Integer.bitCount(x);
cnt.put(c, cnt.getOrDefault(c, 0) + 1);
}
var ans = 0L;
for (var x : cnt.entrySet())
for (var y : cnt.entrySet())
if (x.getKey() + y.getKey() >= k)
ans += (long) x.getValue() * y.getValue();
return ans;
}
}
python3 解法, 执行用时: 120 ms, 内存消耗: 33.8 MB, 提交时间: 2023-08-11 11:01:04
'''
c(x): x的二进制格式1的个数
c(x∣y) + c(x&y) = c(x)+c(y)
进一步地，二重循环可以用前缀和（或者后缀和）来优化。
我们可以从小到大遍历 cnt[c(x)]，由于 c(y)≥k−c(x)c(y)，c(y) 也会从大到小减小，
我们可以用后缀和维护这些 cnt[c(y)] 的和。
'''
class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
cnt = [0] * 30
for x in set(nums):
cnt[x.bit_count()] += 1
ans = 0
s = sum(cnt[k:])
for cx, ccx in enumerate(cnt):
ans += ccx * s
if 0 <= k - 1 - cx < 30:
s += cnt[k - 1 - cx]
return ans
python3 解法, 执行用时: 128 ms, 内存消耗: 34.6 MB, 提交时间: 2023-08-11 10:59:42
'''
c(x): x的二进制格式1的个数
c(x∣y) + c(x&y) = c(x)+c(y)
遍历去重后的 nums，统计 c(nums[i]) 的个数，记录在 cnt 中，然后写一个二重循环遍历 cnt，
对于所有的 c(x)+c(y)≥k 累加 cnt[c(x)]⋅cnt[c(y)]，
表示从这两组中各选一个 x 和 y 组成优质数对的个数（乘法原理）。
'''
class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
cnt = Counter(x.bit_count() for x in set(nums))
ans = 0
for cx, ccx in cnt.items():
for cy, ccy in cnt.items():
if cx + cy >= k: # (x,y) 是优质数对
ans += ccx * ccy
return ans