Dada una array de números enteros arr[] de tamaño N y un número entero K , la tarea es encontrar la K-ésima suma del par más pequeño de la array dada.
Ejemplos:
Entrada: arr[] = {1, 5, 6, 3, 2}, K = 3
Salida: 5
Explicación: La suma de todos los pares es: 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. El tercero más pequeño entre estos es 5.Entrada: arr[] = {2, 4, 5, 6}, K = 6
Salida: 11
Enfoque ingenuo: Este es un enfoque codicioso . Obtendremos las sumas de todos los pares posibles y los almacenaremos en una array. Luego ordenaremos esa array en orden ascendente y el valor K-th es la respuesta requerida.
Complejidad de Tiempo: O (N 2 * log(N 2 ))
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el concepto de este enfoque se basa en max-heap . Implementaremos un montón máximo de tamaño K. Siga los pasos que se mencionan a continuación:
- Comience a iterar la array desde i = 0 hasta i = N-2 .
- Para cada iteración de j = i+1 a j = N-1 .
- Obtenga la suma de este par (i, j) e insértelo en el montón máximo .
- Si el montón está lleno , compare el elemento superior del montón con esta suma .
- Si el valor del elemento superior es mayor , reemplácelo con la nueva suma .
- Cuando la iteración finaliza, el elemento superior del montón máximo es la K-ésima suma del par más pequeño .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to get the Kth smallest pair sum
int kthPairSum(vector<int>& arr, int K)
{
int n = arr.size();
// Priority queue to implement max-heap
priority_queue<int> pq;
// Loop to calculate all possible pair sum
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Variable to store the sum
int temp = arr[i] + arr[j];
// If the heap is full
if (pq.size() == K) {
// If the top element is greater
if (pq.top() > temp) {
pq.pop();
pq.push(temp);
}
}
else
pq.push(temp);
}
}
// Return the Kth smallest value
return pq.top();
}
// Driver code
int main()
{
vector<int> arr = { 1, 5, 6, 3, 2 };
int K = 3;
cout << kthPairSum(arr, K);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG {
// Function to get the Kth smallest pair sum
static int kthPairSum(int[] arr, int K)
{
int n = arr.length;
// Priority queue to implement max-heap
// Creating empty priority queue
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder());
// Loop to calculate all possible pair sum
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Variable to store the sum
int temp = arr[i] + arr[j];
// If the heap is full
if (pq.size() == K) {
// If the top element is greater
if (pq.peek() > temp) {
pq.poll();
pq.add(temp);
}
}
else
pq.add(temp);
}
}
// Return the Kth smallest value
return pq.peek();
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 5, 6, 3, 2 };
int K = 3;
System.out.println(kthPairSum(arr, K));
}
}
// This code is contributed by Potta Lokesh
Python3
from queue import PriorityQueue # Function to get the Kth smallest pair sum def kthPairSum(arr, K): n = len(arr); # Priority queue to implement max-heap pq = PriorityQueue() # Loop to calculate all possible pair sum for i in range(n - 1): for j in range(i + 1, n): # Variable to store the sum temp = arr[i] + arr[j]; # If the heap is full if (pq.qsize() == K): # If the top element is greater if (pq.queue[-1] > temp): pq.get(); pq.put(temp); else: pq.put(temp); # Return the Kth smallest value return pq.queue[0]; # Driver code arr = [ 1, 5, 6, 3, 2 ]; K = 3; print(kthPairSum(arr, K)); # This code is contributed by saurabh_jaiswal.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to get the Kth smallest pair sum
static int kthPairSum(int[] arr, int K)
{
int n = arr.Length;
// Priority queue to implement max-heap
// Creating empty priority queue
List<int> pq = new List<int>();
// Loop to calculate all possible pair sum
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Variable to store the sum
int temp = arr[i] + arr[j];
// If the heap is full
if (pq.Count == K) {
// If the top element is greater
if (pq[0] > temp) {
pq.Remove(0);
pq.Add(temp);
}
}
else
pq.Add(temp);
}
}
// Return the Kth smallest value
return pq[0]-1;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 5, 6, 3, 2 };
int K = 3;
Console.Write(kthPairSum(arr, K));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// Javascript code for the above approach
// Function to get the Kth smallest pair sum
function kthPairSum(arr, K)
{
let n = arr.length;
// Priority queue to implement max-heap
pq = [];
// Loop to calculate all possible pair sum
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
// Variable to store the sum
let temp = arr[i] + arr[j];
// If the heap is full
if (pq.length == K) {
// If the top element is greater
if (pq[0] > temp) {
pq.shift();
pq.push(temp);
pq.sort((a, b) => b - a);
}
}
else
{pq.push(temp);
pq.sort((a, b) => b - a);}
}
}
// Return the Kth smallest value
return pq[0];
}
// Driver code
let arr = [ 1, 5, 6, 3, 2 ];
let K = 3;
document.write(kthPairSum(arr, K));
// This code is contributed by Pushpesh raj
</script>
5
Complejidad de Tiempo: O(N 2 * logK)
Espacio Auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por mekalasiva1995 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA