Задача: 373. Find K Pairs with Smallest Sums
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.

Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

👨‍💻 Алгоритм:

1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.

2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.

3⃣Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.

😎 Решение:

var kSmallestPairs = function(nums1, nums2, k) {
    let m = nums1.length, n = nums2.length;
    let ans = [];
    let visited = new Set();
    let minHeap = new MinHeap();
    minHeap.insert([nums1[0] + nums2[0], 0, 0]);
    visited.add(`0,0`);

    while (k-- > 0 && minHeap.size() > 0) {
        let [sum, i, j] = minHeap.extractMin();
        ans.push([nums1[i], nums2[j]]);

        if (i + 1 < m && !visited.has(`${i + 1},${j}`)) {
            minHeap.insert([nums1[i + 1] + nums2[j], i + 1, j]);
            visited.add(`${i + 1},${j}`);
        }

        if (j + 1 < n && !visited.has(`${i},${j + 1}`)) {
            minHeap.insert([nums1[i] + nums2[j + 1], i, j + 1]);
            visited.add(`${i},${j + 1}`);
        }
    }

    return ans;
};

class MinHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    insert(val) {
        this.heap.push(val);
        this.bubbleUp();
    }

    extractMin() {
        if (this.size() === 1) return this.heap.pop();
        let min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }

    bubbleUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let element = this.heap[index];
            let parentIndex = Math.floor((index - 1) / 2);
            let parent = this.heap[parentIndex];
            if (parent[0] <= element[0]) break;
            this.heap[index] = parent;
            this.heap[parentIndex] = element;
            index = parentIndex;
        }
    }

    bubbleDown() {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild[0] < element[0]) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swap === null && rightChild[0] < element[0]) ||
                    (swap !== null && rightChild[0] < leftChild[0])
                ) {
                    swap = rightChildIndex;
                }
            }

Ставь 👍 и забирай 📚 Базу знаний