2426. 满足不等式的数对数目-二进制树算法解决和暴力解法

2426. 满足不等式的数对数目-二进制树算法解决和暴力解法

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff ，统计满足以下条件的 数对 (i, j) ：

0 <= i < j <= n - 1 且
nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.
1
2

请你返回满足条件的 数对数目 。

示例 1：

输入：nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
输出：3
解释：
总共有 3 个满足条件的数对：

1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。因为 i < j 且 1 <= 1 ，这个数对满足条件。
2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。因为 i < j 且 -2 <= 2 ，这个数对满足条件。
3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。因为 i < j 且 -3 <= 2 ，这个数对满足条件。
   所以，我们返回 3 。

示例 2：

输入：nums1 = [3,-1], nums2 = [-2,2], diff = -1
输出：0
解释：
没有满足条件的任何数对，所以我们返回 0 。

这题用了一个高阶算法-二进制数，也是博主刚学的，感兴趣的可以学习一下:

void insert(int *Btree,int val){
    int index=1;
     int  a=65536;
     int sum=0;
    for(int i=0;i<17;i++){
    
       sum=sum+(val&a);
     
        if(val&a){
          
            index=index*2+1;
           
        }
        else{
            index=index*2;
        }
       
    
         Btree[index]++;
        a=a>>1;
       
    }
      
    
}


long long count(int *Btree,int val){
    int index=1;
    long long re=0;
    int  a=65536;
    for(int i=0;i<17;i++){
      //  printf("%d ",index);
       
      if(val&a){
         // printf("||%d ",index*2);
          re=re+Btree[index*2];
           index=index*2+1;
            
           
          
           
        }
        else{
            index=index*2;
        }
        a=a>>1;
       
    }
    re=re+Btree[index];

      return re;
}

long long numberOfPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int diff){
    int aid_arr[nums1Size];
    int *Btree=(int *)malloc(sizeof(int )*65536*4);
    for(int  i=0;i<65536;i++){
       Btree[i]=0;
    }
     for(int  i=0;i<nums1Size;i++){
        aid_arr[i]=nums1[i]-nums2[i]+32768+20001;
    }
    long long re=0;
    for(int i=0;i<nums1Size;i++){
      
        long long count_n=count(Btree,aid_arr[i]+diff);
        insert(Btree,aid_arr[i]);
        re=re+count_n;
         
        
      
       

    }
    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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

下面则是暴力解法的代码，时间复杂度不能通过，但是解题过程还是可行的。

long long numberOfPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int diff){
    int aid_arr[nums1Size];
    for(int  i=0;i<nums1Size;i++){
        aid_arr[i]=nums1[i]-nums2[i];
    }
    long long re=0;
    for(int i=1;i<nums1Size;i++){
        for(int j=0;j<i;j++){
            if(aid_arr[i]+diff>=aid_arr[j]){
                re++;

            }
        }

    }
    return re;



}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21