День 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 дней программирования и присоединяйтесь ко мне в этом путешествии.
Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в качестве комментариев вместе со ссылкой на описание проблемы.
Увидимся завтра!
Ваше здоровье!