K-я наименьшая сумма пар в заданном массиве
Дан массив целых чисел 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)