373.查找和最小的K对数字

链接：373.查找和最小的K对数字
难度：Medium
标签：数组、堆（优先队列）
简介：找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。

题解 1 - cpp

• 编辑时间：2022-01-14
• 执行用时：924ms
• 内存消耗：62.6MB
• 编程语言：cpp
• 解法介绍：堆。

class Solution {
   public:
    struct node {
        int num1, num2, sum;
        bool operator<(const node& obj) const {
            return sum == obj.sum
                       ? num2 == obj.num2 ? num1 < obj.num1 : num2 < obj.num2
                       : sum < obj.sum;
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2,
                                       int k) {
        priority_queue<node> q;
        int isBreak = 0, len = min(k, (int)(nums1.size() * nums2.size()));
        // cout << "len = " << len << endl;
        vector<vector<int>> ans(len, vector<int>(2));
        for (auto& num1 : nums1) {
            if (isBreak) break;
            for (auto& num2 : nums2) {
                if (q.size() >= len && num1 > 0 && num2 > 0 &&
                    num1 > q.top().sum && num2 > q.top().sum)
                    isBreak = 1;
                if (isBreak) break;
                if (q.size() < len) {
                    q.push((node){num1, num2, num1 + num2});
                } else if (q.top().sum > num1 + num2) {
                    // cout << q.top().num1 << ',' << q.top().num2;
                    // if (q.top() )
                    q.pop();
                    q.push((node){num1, num2, num1 + num2});
                }
            }
        }
        while (q.size()) {
            node n = q.top();
            q.pop();
            ans[len - 1][0] = n.num1;
            ans[len - 1][1] = n.num2;
            len--;
        }
        return ans;
    }
};

题解 2 - typescript

• 编辑时间：2021-04-09
• 执行用时：2136ms
• 内存消耗：77MB
• 编程语言：typescript
• 解法介绍：构建堆。

class Heap<T> {
  private arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  constructor(private compare: (num1: T, num2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 < this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
}
function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
  const sum = (arr: number[]) => arr.reduce((total, cur) => total + cur, 0);
  const heap = new Heap<number[]>((nums1, nums2) => sum(nums2) - sum(nums1));
  nums1.forEach(num1 => nums2.forEach(num2 => heap.add([num1, num2])));
  const ans: number[][] = [];
  while (heap.size && k--) ans.push(heap.remove());
  return ans;
}