K-я наименьшая сумма пар в заданном массиве

Опубликовано: 20 Сентября, 2022

Дан массив целых чисел arr[] размера N и целое число K , задача состоит в том, чтобы найти K-ю наименьшую сумму пар данного массива.

Примеры:

Input: arr[] = {1, 5, 6, 3, 2}, K = 3
Output: 5
Explanation: The sum of all the pairs are: 1+5 = 6, 1+6 = 7, 1+3 = 4, 1+2 = 3, 5+6 = 11, 5+3 = 8, 5+2 = 7, 6+3 = 9, 6+2 = 8, 2+3 = 5. The 3rd smallest among these is 5.

Input: arr[] = {2, 4, 5, 6}, K = 6
Output: 11

Наивный подход: это жадный подход. Мы получим суммы всех возможных пар и сохраним их в массиве. Затем мы отсортируем этот массив в порядке возрастания, и K-е значение будет искомым ответом.
Временная сложность: O (N 2 * log(N 2 ))
Вспомогательное пространство: O(N 2 )

Эффективный подход . Концепция этого подхода основана на максимальной куче. Мы будем реализовывать максимальную кучу размером K. Выполните шаги, указанные ниже:

  • Начните перебирать массив от i = 0 до i = N-2 .
    • Для каждого i выполните итерацию от j = i+1 до j = N-1 .
    • Получите сумму этой пары (i, j) и вставьте ее в максимальную кучу .
    • Если куча заполнена , сравните верхний элемент кучи с этой суммой .
    • Если значение верхнего элемента больше , замените его новой суммой .
  • Когда итерация завершена, самым верхним элементом max-heap является K-я наименьшая парная сумма .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N 2 * logK)
Вспомогательное пространство: O(K)

РЕКОМЕНДУЕМЫЕ СТАТЬИ