LeetCode 2354. 优质数对的数目 二进制01表示和集合之间的转换

给你一个下标从 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-excellent-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

总而言之

这道题的关键点就在于题目中定义的那个运算。为什么要定义那样的运算？这种运算有啥性质？

首先，与运算和或运算不会让总的1的个数减少。两个数与加上两个数或就等于

(2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。

例如 x=110x=110，y=011y=011，只统计一次的部分为 x’=100x
′
=100，y’=001y
′
=001，统计了两次的部分为 x&y=010x&y=010。我们可以直接把 010010 重新分配到 x’x
′
和 y’y
′
上，这样又得到了 xx 和 yy。

记 c(x)c(x) 为 xx 的二进制表示中的 11 的个数，则有如下等式：

c(x|y)+c(x&y)=c(x)+c(y)
c(x∣y)+c(x&y)=c(x)+c(y)

另外一种思路是把二进制数看成集合，根据容斥原理 |A∪B∣=∣A∣+∣B∣−∣A∩B∣，得
∣A∪B∣+∣A∩B∣=∣A∣+∣B∣

现在就转换成找两个数，这俩数中二进制表示里边1的个数之和大于等于k就行了。但是数太多了，总不能暴力，这样时间复杂度10^10了。

考虑到数最大10^9有不超过30个1。因此，可以开一个cnt[30]，cnt[i]就表示二进制表示中1的个数为i的数有多少个。

注意：
自己和自己也可以，俩数换换位置也可以，但是记得给原来的数组去重，否则会多次统计，影响正确。

class Solution {
    
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
    
        typedef long long LL;

        // 去重
        sort(nums.begin(), nums.end());
        // unique函数会将数组里连续相同的数删掉只剩一个，然后返回最后位置的下一个位置，然后将这个位置到最后一个位置删掉就可以了
        nums.erase(unique(nums.begin(), nums.end()), nums.end());

        // 初始化记录1的个数的数组
        int cnt[30] = {
    0};
        for(auto x: nums){
    
            int s = 0;
            while(x) s += x & 1, x >>= 1;
            cnt[s] ++;
        }

        // 遍历
        LL res = 0;
        for(int i = 0; i < 30; i ++)
            for(int j = 0; j < 30; j ++)
                if(i + j >= k)
                    res += (LL)cnt[i] * cnt[j];
        return res;
    }
};

Python:

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        # 使用Counter统计, bit_count返回有几个1，set对原来的数组去重
        cnt = Counter(x.bit_count() for x in set(nums))
        ans = 0 
        # cnt是个字典，就是cnt[30]
        for cx, ccx in cnt.items():
            for cy, ccy in cnt.items():
                if cx + cy >= k:
                    ans += ccx * ccy
        
        return ans

复杂度分析

时间复杂度：O(n+U^2) 其中 n为 nums 的长度，U为不同的 c(nums[i]) 的个数，不超过 30。
空间复杂度：O(n+U)。

后缀和优化

# 后缀和优化，因为cx + cy >= k, 当遍历到cy之后， cy - 30的都是可以的了
        cnt = [0] * 30
        for x in set(nums):
            cnt[x.bit_count()] += 1
        ans = 0
        # 先把cnt[k] 到 cnt[30] 求和
        s = sum(cnt[k:])
        # 从前往后遍历
        for cx, ccx in enumerate(cnt):
            ans += ccx * s
            # 当前遍历到的索引为cx， 那么末尾的为k - cx
            if  0 <= k - 1 - cx < 30:
                # 处理后缀和
                s += cnt[k - 1 - cx]
        return ans