Почему это работает
- nums2 отсортирован, поэтому каждая строка сумм растёт вправо. Пары — это k отсортированных списков, по одному на строку, и следующая наименьшая сумма — всегда первая неиспользованная пара какой-то строки.
- В куче лежит как раз первая неиспользованная пара каждой строки, поэтому наверху следующая наименьшая сумма. После того как пару достали, строка сдвигается на одну пару.
- Прогон кончается после k извлечений: пары правее в строках даже не строятся, как пары с 9 здесь.
Сложность
Время O(n + k log n), где n — длина nums1: куча из одной пары на строку, затем k извлечений и не больше k добавлений. Память O(n + k) на кучу и ответ.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗