День 28: Задача «Найти K пар с наименьшими суммами»

Проблема:

Вам даны два целочисленных массива nums1 и nums2, отсортированные в порядке возрастания, и целое число k.

Определите пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.

Найдите k пар (u1, v1), (u2, v2)… (uk, vk) с наименьшими суммами.

Пример 1:

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]

Пример 2:

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

Пример 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [1,3],[2,3]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

Решение:

import heapq
class MaxHeapObj(object):
    def __init__(self, val): self.val = val
    def __lt__(self, other): return self.val > other.val
    def __eq__(self, other): return self.val == other.val
    def __str__(self): return str(self.val)
    
def kSmallestPairs(self, nums1, nums2, k):
    if not nums1 or not nums2 or not k:
        return []
    target = []
    count = 0
    for n1 in nums1:
        for n2 in nums2:
            sum = n1 + n2
            if(count < k):
                heapq.heappush(
                    target, 
                    MaxHeapObj((sum, [n1,n2]))
                )
            else:
                if(target[0].val[0] > sum):
                    heapq.heappop(target)
                    heapq.heappush(
                        target, 
                        MaxHeapObj((sum, [n1,n2]))
                    ) 
            count += 1
    final = []
    for _ in range(k):
        if len(target) > 0:
            x, y = heapq.heappop(target).val
            final.append(y)
    return final

Пояснение:

Это вариант задачи K-й самый большой элемент в массиве. Я бы порекомендовал вам сначала прочитать это, прежде чем погрузиться в это.

В этой задаче мы использовали min-heap, чтобы найти k-й по величине элемент. Как мы там обсуждали, чтобы найти k-е наименьшее, нам понадобится max-heap.

Чтобы найти k наименьших пар, нам понадобится максимальная куча размером k. Идея состоит в том, чтобы взять все комбинации элементов из обоих списков и продолжать добавлять их в максимальную кучу, пока она не заполнится.

После заполнения максимальной кучи мы сравниваем сумму новой пары с верхним элементом максимальной кучи. Мы выталкиваем и добавляем наш новый элемент, только если новая сумма меньше суммы максимальной пары в куче

Когда мы закончим обработку всех пар, пара в нашей максимальной куче станет k наименьших пар.

Вот и все. Вот как вы решаете задачу «Найти K пар с наименьшими суммами».

Если вы заинтересованы в решении других проблем, следуйте 60 дней программирования и присоединяйтесь ко мне в этом путешествии.

Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в качестве комментариев вместе со ссылкой на описание проблемы.

Увидимся завтра!

Ваше здоровье!