2354. 优质数对的数目-排序去重，加统计

2354. 优质数对的数目-排序去重，加统计

给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。

如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：

num1 和 num2 都 在数组 nums 中存在。
num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。
1
2

返回 不同 优质数对的数目。

如果 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的个数，解题代码如下：

int cmp(const void* a, const void* b) {

    return *(int*)a - *(int*)b;

}

long long countExcellentPairs(int* nums, int numsSize, int k){
    long long re=0;
    int r[32];

    int newsize = 0;
    qsort(nums, numsSize, sizeof(int), cmp);    //排序原数组

    for (int i = 1; i < numsSize; i++) {

        if (nums[i] != nums[newsize]) nums[++newsize] = nums[i];

    }//去重原数组

    ++newsize;  

    
   // printf("newsize %d ",newsize);
    numsSize=newsize;


    for(int i=0;i<32;i++){
        r[i]=0;
    }
     for(int i=0;i<numsSize;i++){
         int count=0;
         int t=nums[i];
         while(t){
             if(t&1){
                 count++;
             }
             t=t>>1;
         }
         r[count]++;
      
    }
    //  for(int i=0;i<32;i++){
    //     printf("%d ",r[i]);
    // }
    for(int i=0;i<32;i++){
        if(r[i]!=0){
            for(int j=i;j<32;j++){
                if(r[j]!=0){
                    if(i+j>=k&&i==j){
                        re=re+(r[j])*(r[j]-1)+r[j];


                    }
                    else if(i+j>=k){
                        re=re+r[i]*r[j]*2;
                    }
                }
            }
        }
    }
    return re;


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64