[路飞]_leetcode-373-查找和最小的K对数字

输入: 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]
复制代码

输入: 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]
复制代码

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

// 实现大顶堆
class BigHeap {
  constructor(k){
    this.arr = [];
    this.size = 0;
    this.max = k;
  }
  // 插入操作
  push(item){
    this.arr.push(item);
    this.size++;
    if(this.size>1){
      let cur = this.size-1,
      parent = (cur-1)>>1;
      while(cur>0&&compare(this.arr[cur],this.arr[parent])){
        [this.arr[parent],this.arr[cur]] = 
        [this.arr[cur],this.arr[parent]];
        cur = parent;
        parent = (cur-1)>>1;
      }
    }
    if(this.size>this.max) this.pop();
  }
  // 弹出操作
  pop(){
    this.arr[0] = this.arr.pop();
    this.size--;
    let cur = 0,
    childl = cur*2+1,
    childr = cur*2+2;
    while(
      (childl<this.size&&compare(this.arr[childl],this.arr[cur])) ||
      (childr<this.size&&compare(this.arr[childr],this.arr[cur]))
    ){
      if(childr<this.size&&compare(this.arr[childr],this.arr[childl])){
        [this.arr[cur],this.arr[childr]] = 
        [this.arr[childr],this.arr[cur]];
        cur = childr;
      }else{
        [this.arr[cur],this.arr[childl]] = 
        [this.arr[childl],this.arr[cur]];
        cur = childl;
      }
      childl = cur*2+1,
      childr = cur*2+2;
    }
  }
  // 获取堆顶元素
  top(){
    return this.arr[0]
  }
}
// 比较两数组之和大小
function compare(arr1,arr2){
  return (arr1[0]+arr1[1])>(arr2[0]+arr2[1])
}
var kSmallestPairs = function(nums1, nums2, k) {
  // 实例化大顶堆
  const heap = new BigHeap(k);
  // 遍历每一种组合
  for(let i = 0;i<nums1.length;i++){
    for(let j = 0;j<nums2.length;j++){
      const item = [nums1[i],nums2[j]];
      // 只有当堆中元素数量小于k个或者当前数对之和小于堆顶元素时才插入堆中
      if(heap.size<k || compare(heap.top(),item)){
        heap.push(item);
      }else{
        // 如果当前数对大于堆顶元素，那么本次循环后续数对也一定大于堆顶元素，退出当前循环
        break;
      }
    }
  }
  // 返回堆中保存数对
  return heap.arr;
};
复制代码