`算法竞赛知识` `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
解释：该数组中不存在优质数对。

提示：

1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
1 < = n u m s [ i ] < = 1 0 9 1 <= nums[i] <= 10^9 1<=nums[i]<=109
1 < = k < = 60 1 <= k <= 60 1<=k<=60

定义: count( x)为, x这个数的二进制中1的个数

对于优质数对(a, b), 他的值为: count( a & b) + count( a | b)
由于count函数, 和 & |操作, 都是满足 二进制拆分, 即我们可以把每一位给拆分开来看

而如果某一位的ab是: 1 1, 则其对答案的贡献是2 (对&贡献1, 对|贡献1)
而如果某一位的ab是: 1 0, 则其对答案的贡献是1 (对&贡献0, 对|贡献1)
而如果某一位的ab是: 0 1, 则其对答案的贡献是1 (对&贡献0, 对|贡献1)
而如果某一位的ab是: 0 0, 则其对答案的贡献是0 (对&贡献0, 对|贡献1)

惊奇的发现: (a, b) = count( a & b) + count( a | b) = count( a) + count( b)

由于数对是以值作为唯一性标准, 所以, 对num数组进行unique操作后
答案为: 从num数组中, 任意选两个下标i, j(可以相同), 使得: count( num[ i]) + count( num[ j]) >= k

可以再转换一下:
令c数组为: c[ i] = count( num[ i])
任意选两个下标i, j(可以相同), 使得: c[ i] + c[ j] >= k

这可以通过双指针;
(1, 将c进行排序) (2, 设置一个全局的l = 0端点)

int l = 0;
FOR_RE_( i, n-1, 0, 1){
    while( l <= i){
        if( c[ l] + c[ i] >= k){
            break;
        }
        ++ l;
    }
    if( l > i){ break;}
    ans += (i - l) * 2; //< (l, i) 且(l < i)的话, 其(l,r) (r,l)都是答案
    ans ++; //< (i, i)
}