leetcode-6127：优质数对的数目

题目

题目连接
给你一个下标从 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
解释：该数组中不存在优质数对。

解题

方法一：等价转换

对于 x|y 和x&y中的 1，在同一个比特位上，如果都有 1，那这个 1 会被统计两次；如果一个为 1 另一个为 0，那这个 1 会被统计一次。
因此可以等价替换，与、或结果 的二进制位1的个数 和，就是两个数分别二进制位1的个数和。

参考链接

class Solution {
    
public:
    int getBits(int num){
    
        int res=0;
        while(num){
    
            res+=num&1;
            num>>=1;
        }
        return res;
    }

    long long countExcellentPairs(vector<int>& nums, int k) {
    

        //去重
        sort(nums.begin(),nums.end());
        nums.resize(unique(nums.begin(),nums.end())-nums.begin());
        // nums.erase(unique(nums.begin(),nums.end()),nums.end()); //这两种都可以

        int n=nums.size();
        vector<int> cnt(64,0);//bits个数 ---->数量
        for(int i=0;i<n;i++){
    
            int bits=getBits(nums[i]);//求位1的数量
            cnt[bits]++;
        }
        long long res=0;
        for(int i=1;i<=60;i++){
    
            for(int j=1;j<=60;j++){
    
                if(i+j>=k){
    
                    res+=1ll*cnt[i]*cnt[j];
                }
            }
        }
        return res;
    }
};