优质数对的数目

标签: 位运算 数组 哈希表 二分查找

难度: Hard

给你一个下标从 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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 60

Submission

运行时间: 80 ms

内存: 32.1 MB

from collections import Counter

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        cnt = Counter(map(int.bit_count,set(nums)))
        res = 0
        for i, u in cnt.items():
            for j, v in cnt.items():
                if i + j >= k:
                    res += u * v
        return res

Explain

该题解的思路是首先对数组去重，然后统计每个数字的二进制表示中1的个数，用Counter来计数各个位数的数字出现的次数。之后，遍历Counter的每一对位数(i, j)，如果两者之和大于等于k，则说明这两个位数的数字组合成的数对满足条件，应该将它们出现的次数相乘，并累加到结果中。

时间复杂度: O(n^2)

空间复杂度: O(n)

from collections import Counter

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 统计每个数字的二进制中1的个数
        cnt = Counter(map(int.bit_count,set(nums)))
        res = 0
        # 遍历每一对位数组合
        for i, u in cnt.items():
            for j, v in cnt.items():
                if i + j >= k:
                    res += u * v
        return res

Explore

去重操作是为了确保每个数字在最终的统计中只被计算一次。如果不进行去重，同一个数字的重复出现会导致其二进制中1的个数被多次计算，从而影响最终计数器（Counter）中各个位数的计数结果。这会导致在计算满足条件的数对时，重复数字的贡献被错误地放大，从而得到一个不准确的结果。因此，通过去重，我们能确保每个数字对应的位数只被统计一次，这有助于正确计算满足条件的数对总数。

是的，题解的逻辑中确实指出只有当两个位数的和大于等于k时，这两个位数对应的数字组合才被认为是优质数对，因此符合要求。对于i + j < k的情况，这些数对的位数和不满足给定的阈值k，因此它们可以被忽略不计。这是基于题目条件设定的，即只有位数和满足或超过k的数对才被视为有效，从而减少不必要的计算和提高算法效率。

在算法中，遍历Counter确实会遇到(i, u)和(j, v)相同的情况，即当i等于j时。在这种情况下，我们依然需要计算这样的数对，但是计算方式略有不同。对于i等于j的情况，实际上是在计算同一个位数的数字组合，因此应该计算的是这个位数数字出现次数的平方，即u * u。但是，如果直接这样计算会导致每个组合被计算两次（一次为(i, j)，一次为(j, i)），因此需要特殊处理以避免重复计算。一种常见的处理方式是在计算时只考虑i <= j的情况，并在i = j时按u * u处理，而在i < j时按u * v处理。