这道题的核心在于一个巧妙的位运算性质转换,理解了它,代码就很简单了。

核心性质:  
对于任意两个数 num1 和 num2,(num1 & num2) 和 (num1 | num2) 的二进制中 1 的个数之和,等于 num1 和 num2 各自二进制中 1 的个数之和。

所以,优质数对的条件就等价于:两个数的二进制 1 的个数之和 ≥ k。

Python3 实现:

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 1. 去重
        unique_nums = set(nums)
        
        # 2. 统计每种 1 的个数的数字数量(最多 32 位)
        cnt = [0] * 33
        for num in unique_nums:
            # bit_count() 是 Python 3.8+ 内置方法,统计二进制中 1 的个数
            cnt[num.bit_count()] += 1
        
        # 3. 计算答案
        ans = 0
        for i in range(33):
            for j in range(33):
                if i + j >= k:
                    ans += cnt[i] * cnt[j]
        
        return ans

另一种写法(更 Pythonic,用 Counter):

from collections import Counter

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 用 Counter 一步到位统计每种 1 的个数的数量
        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:
                    ans += ccx * ccy
        
        return ans

复杂度分析:
- 时间复杂度:O(n + 32²),其中 n 是数组长度,32 是常数,所以近似 O(n)。
- 空间复杂度:O(n),用于去重。

注意:  
- bit_count() 是 Python 3.8+ 引入的方法,如果环境版本较低,可以用 bin(x).count('1') 替代。
- 题目中 k 最大为 60,而数字最大 10⁹ 只有 30 位二进制,所以 32 的循环范围完全够用。

 

更多推荐