LeetCode 题解工作台
优质数对的数目
给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。 如果满足下述条件，则数对 (num1, num2) 是 优质数对 ： num1 和 num2 都 在数组 nums 中存在。 num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class Solution: def countExcellentPairs(self, nums: List[int], k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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
解题思路
方法一
class Solution:
def countExcellentPairs(self, nums: List[int], k: int) -> int:
s = set(nums)
ans = 0
cnt = Counter()
for v in s:
cnt[v.bit_count()] += 1
for v in s:
t = v.bit_count()
for i, x in cnt.items():
if t + i >= k:
ans += x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting and binary search over unique bit counts, space complexity is O(n) to store counts and hash map entries. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for handling duplicates correctly to prevent overcounting.
- question_mark
Expect candidates to optimize bit counting rather than comparing numbers directly.
- question_mark
Check if the candidate uses array scanning plus hash lookup efficiently for large n.
常见陷阱
外企场景- error
Failing to deduplicate nums before counting excellent pairs, which inflates results.
- error
Using nested loops on all pairs leading to TLE for large arrays.
- error
Miscounting set bits or misunderstanding the combined AND and OR bit sum condition.
进阶变体
外企场景- arrow_right_alt
Count excellent pairs where only the OR bits count towards k instead of AND plus OR.
- arrow_right_alt
Find excellent pairs in a multidimensional array or matrix using similar bit manipulation.
- arrow_right_alt
Compute excellent pairs with an added constraint on the difference between numbers.