373. 查找和最小的 K 对数字-暴力解法和多路归并思想+败者树+大顶堆算法（高阶算法）

373. 查找和最小的 K 对数字-暴力解法

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes){
    int **re=(int **)malloc(sizeof(int *)*k);
    (* returnColumnSizes)=(int *)malloc(sizeof(int)*k);
    int adress[nums1Size];
    for(int i=0;i<nums1Size;i++){
        adress[i]=0;
    }
     for(int i=0;i<k;i++){
        re[i]=(int *)malloc(sizeof(int)*2);
        (* returnColumnSizes)[i]=2;
    }
    int size=0;

    while(size<k){
        int i=0;
        while(adress[i]>=nums2Size){
            i++;
            if(i==nums1Size){
                break;
            }
        }
        if(i==nums1Size){
                break;
            }
        int min_index=i,min=nums1[i]+nums2[adress[i]];

        
        for(;i<nums1Size;i++){
            if(adress[i]<nums2Size&&nums1[i]+nums2[adress[i]]<min){
                min_index=i;
                min=nums1[i]+nums2[adress[i]];

            }
        }
         
        if(adress[min_index]>=nums2Size){
            break;
        }
       
        re[size][0]=nums1[min_index];
         re[size][1]=nums2[adress[min_index]];
        adress[min_index]++;
        size++;
        printf("fa");
         

       
    }
      *returnSize=size;

    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

这题的一个优化其实类似于败者树算法，同时借助了多路归并的一个思想，实际上败者树本身也就是借助堆实现的，代码强度很高，但是值得学习，因为，这题的解题思路非常新颖，平时大家应该很少能见到，而且，这在多路归并分布式处理数据中，该算法思想都能借鉴
解题代码如下：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

//adress存储 nums2,adress_numszie1_index存储nums1

 void adjsut_top(int **adress,int nums1Size,int k,int *nums1,int *nums2){
     while(k<nums1Size/2){
         int min_index;
         int c=nums1[adress[k][0]]+nums2[adress[k][1]];
         if(k*2+1<nums1Size-1){
             int a=nums1[adress[k*2+1][0]]+nums2[adress[k*2+1][1]];
             int b=nums1[adress[k*2+2][0]]+nums2[adress[k*2+2][1]];
             if(a>b){
               min_index=k*2+2;
             }
             else{
                 min_index=k*2+1;
             }

         }
         else{
             min_index=k*2+1;
         }
         if(c>re_adress(adress,min_index,nums1,nums2)){
           
             int t=adress[k][0];
             adress[k][0]=adress[min_index][0];
             adress[min_index][0]=t;

             t=adress[k][1];
            adress[k][1]=adress[min_index][1];
            adress[min_index][1]=t;
             k=min_index;

         }
         else{
             break;
         }

         

         
     }



        
    

 }
 int re_adress(int **adress,int index,int *nums1,int *nums2){
     return nums1[adress[index][0]]+nums2[adress[index][1]];
 }

void  create_top(int *adress,int nums1Size,int *nums1,int *nums2){
    for(int i=nums1Size/2-1;i>=0;i--){
        adjsut_top(adress,nums1Size,i,nums1,nums2);

    }


} 
int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes){
    int **re=(int **)malloc(sizeof(int *)*k);
    (* returnColumnSizes)=(int *)malloc(sizeof(int)*k);
    int** adress=(int **)malloc(sizeof(int*)*nums1Size);
  
    for(int i=0;i<nums1Size;i++){
        adress[i]=(int *)malloc(sizeof(int)*2);
        adress[i][0]=i;
        adress[i][1]=0;
       
    }
     for(int i=0;i<k;i++){
        re[i]=(int *)malloc(sizeof(int)*2);
        (* returnColumnSizes)[i]=2;
    }
    create_top(adress,nums1Size,nums1,nums2);

 
  int n1=nums1Size;


    int size=0;
     while(size<k){
         int index1=adress[0][0],index2=adress[0][1];
           re[size][0]=nums1[index1];
          re[size][1]=nums2[index2];
      
       
      size++;
         if(index2<nums2Size-1){
             adress[0][0]=index1;
             adress[0][1]=index2+1;
         }
         else{
              adress[0][0]=adress[n1-1][0];
             adress[0][1]=adress[n1-1][1];
             n1--;
             
         }
        
  
        if(n1==0){
            break;
        }
        
         adjsut_top(adress,n1,0,nums1,nums2);

     }
    // while(size
    //     int i=0;
    //     while(adress[i]>=nums2Size){
    //         i++;
    //         if(i==nums1Size){
    //             break;
    //         }
    //     }
    //     if(i==nums1Size){
    //             break;
    //         }
    //     int min_index=i,min=nums1[i]+nums2[adress[i]];

        
    //     for(;i
    //         if(adress[i]
    //             min_index=i;
    //             min=nums1[i]+nums2[adress[i]];

    //         }
    //     }
         
    //     if(adress[min_index]>=nums2Size){
    //         break;
    //     }
       
    //     re[size][0]=nums1[min_index];
    //      re[size][1]=nums2[adress[min_index]];
    //     adress[min_index]++;
    //     size++;
      
         

       
    // }
      *returnSize=size;

    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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153