优质对数的数目

Leetcode Link: 6127. 优质数对的数目 - 力扣（LeetCode）

题目

给你一个下标从 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) 也可以是优质数对。

解法一

思路： 仔细思考本题

设函数 c(x) 的输出为数字 x 二进制表示下的 1 的数量 本题题目：c(n1 AND n2) + c(n1 OR n2) >=k 的 n1 和 n2 组成的数对为”优质数对”

通过草稿演算，我们有

c(n1 AND n2) + c(n1 OR n2) = c(n1) + c(n2)

故本题只需要考虑两个数字的 1 数量的总和即可。

1. 去重（这一步在任何题目里都要先考虑，重复究竟对于结果有没有影响）
2. 统计所有数字 1 的个数
3. 按照所含有 1 的数量对去重后的结果进行分组
4. 每两组比较，若含有1的总数>k，则这两组中任意两对都是优质数组

题解：

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        nums = set(nums) #去重
        cnt = [n.bit_count() for n in nums] # 统计1的个数
        counter = Counter(cnt) #按照1的个数分组，其实就是计数 {num of 1: how many numbers}
 
        res = 0
        # 两组两组比较
        for k1, v1 in counter.items():
            for k2, v2 in counter.items():
                if k1 + k2 >= k:
                    res += (v1 * v2)
        
        return res
 

启发和联系

参考Python-二进制相关函数