Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

Given two ascending integer arrays nums1 and nums2, and an integer k.

Define a pair of values (u,v) where the first element comes from nums1 and the second from nums2.

Find the sum of the smallest k-pair numbers (U1,v1), (u2,v2)… Vitamin k (UK).

Example 1:

Enter: nums1 = [1.7.11], nums2 = [2.4.6], k = 3Output:1.2], [1.4], [1.6] returns the front of a sequence3Log:1.2], [1.4], [1.6], [7.2], [7.4], [11.2], [7.6], [11.4], [11.6]
Copy the code

Their thinking

We hold the elements in one array and then iterate over the sum in the other. We then maintain a large root heap of size K and compare each combination to the top element. If it is smaller than the top element, we add it to the large root heap. If it is larger than the top element, since the array is ordered, we terminate the current loop and proceed to the next loop. If the heap size exceeds K, pop the top element.

The problem solving code

function swap(heap, index, parent) {
    [heap[index], heap[parent]] = [heap[parent], heap[index]]
}
function shiftUp(heap, i) {
    const parent = (i - 1) / 2 | 0
    if (sum(heap[i]) > sum(heap[parent])) {
        swap(heap, i, parent)
        shiftUp(heap, parent)
    }
}
function sum(arr) {
    return arr[0] + arr[1];
}
function shiftDown(heap, index) {
    let left = index * 2 + 1;
    if (left >= heap.length) return;
    if (left + 1 < heap.length && sum(heap[left]) < sum(heap[left + 1])) {
        left = left + 1;
    }
    if (sum(heap[index]) <= sum(heap[left])) {
        swap(heap, index, left)
        shiftDown(heap, left)
    }
}
var kSmallestPairs = function (nums1, nums2, k) {
    const heap = [];
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            if (heap.length < k) {
                heap.push([nums1[i], nums2[j]]);
                shiftUp(heap, heap.length - 1);
            } else if ((nums1[i] + nums2[j]) <= sum(heap[0])) {
                heap[0] = [nums1[i], nums2[j]];
                shiftDown(heap, 0); }}}return heap.sort((a, b) = > (a[0] + a[1]) - (b[0] + b[1]));
};
Copy the code

conclusion

Use heap way to solve problems, the most basic is to be able to write their own adjustment of a heap into a large root heap or a small root heap, with this foundation, when solving related problems will be handy.