Find K Pairs with Smallest Sums

Средняя№373слияние k списков

Даны два массива, отсортированные по возрастанию, и число k. Пара — это по одному числу из каждого массива. Нужно вернуть k пар с наименьшими суммами. Наш пример: [1, 4, 6], [2, 3, 9] и k = 4 — ответ [1, 2], [1, 3], [4, 2] и [4, 3], их суммы 3, 4, 6 и 7.

373 Find K Pairs with Smallest SumsРазбор · 1×

Пример: nums1 = [1, 4, 6], nums2 = [2, 3, 9], k = 4. В строке i — суммы nums1[i] + nums2[j]; каждая строка растёт вправо, как отсортированный список.

nums2239nums1[0] = 13410nums1[1] = 46713nums1[2] = 68915кучаменьшее слева368result—
ещё не в кучев кучетолько что достали или добавилиуже в result

Каждая строка начинается с первой пары, nums2[0] = 2: суммы 3, 6 и 8 идут в кучу

01/24
сначала · назад · пуск · шаг
Скорость
1function kSmallestPairs(nums1, nums2, k):
2 heap = min-heap of (nums1[i] + nums2[0], i, 0) for each i
3 result = []
4 while size of result < k and heap is not empty:
5 (s, i, j) = pop min from heap
6 add [nums1[i], nums2[j]] to result
7 if j + 1 < len(nums2):
8 push (nums1[i] + nums2[j + 1], i, j + 1) into heap
9 return result
состояние
heap
[3, 6, 8]
result
–
s
–
i
–
j
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. nums2 отсортирован, поэтому каждая строка сумм растёт вправо. Пары — это k отсортированных списков, по одному на строку, и следующая наименьшая сумма — всегда первая неиспользованная пара какой-то строки.
  2. В куче лежит как раз первая неиспользованная пара каждой строки, поэтому наверху следующая наименьшая сумма. После того как пару достали, строка сдвигается на одну пару.
  3. Прогон кончается после k извлечений: пары правее в строках даже не строятся, как пары с 9 здесь.

Сложность

Время O(n + k log n), где n — длина nums1: куча из одной пары на строку, затем k извлечений и не больше k добавлений. Память O(n + k) на кучу и ответ.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.