Dadas dos arrays arr1[] y arr2[] de pares de la forma {ID, valor} de tamaño N y M respectivamente y un objetivo entero , la tarea es encontrar todos los pares de ID de ambas arrays de modo que la suma de los valores de los pares es máximo y tiene un valor como máximo M .
Ejemplos:
Entrada: arr1[] = [[1, 2000], [2, 3000], [3, 2000]], arr2[] = [[1, 2500], [2, 3000], [3, 3000]], destino = 6000
Salida:
2 2
2 3
Explicación:
Los siguientes son los pares de elementos de las dos arrays arr1[] y arr2[]:
- (arr1[2], arr2[2]): La suma de los elementos 3000 + 3000 = 6000(= objetivo) y más cercano al valor objetivo. Imprima los ID como (2, 2).
- (arr1[2], arr2[3]): La suma de los elementos 3000 + 3000 = 6000(= objetivo) y más cercano al valor objetivo. Imprima los ID como (2, 3).
Entrada: arr1[] = [[1, 2000], [2, 3000], [3, 2000]], arr2[] = [[1, 3000], [2, 3000]], destino = 5500 Salida
:
1 1
1 2
3 1
3 2
Enfoque: el problema dado se puede resolver utilizando la estructura de datos TreeMap para almacenar los elementos de la array arr1[] y encontrar eficientemente el par para cada elemento en la otra array arr2[] . A continuación se muestran los pasos:
- Cree un TreeMap donde la clave es el valor del elemento de la array y el valor es la lista de ID .
- Itere la array arr1[] e inserte sus elementos en el TreeMap.
- Inicialice una variable, diga el objetivo más cercano para realizar un seguimiento del valor más cercano al objetivo y no excederlo.
- Inicialice un resultado de ArrayList para almacenar todos los posibles pares de ID.
- Itere la array arr2[] y para cada elemento calcule el valor restante que se buscará en el TreeMap.
- Si el valor restante, digamos (target – arr2[i]) es menor que 0 , entonces no se puede formar el par, así que continúe con la iteración .
- Use la función FloorKey() de TreeMap para encontrar un valor menor o igual que el valor restante. Si el valor devuelto de la función anterior es nulo , entonces no se encuentra ningún elemento correspondiente.
- Si el valor devuelto, digamos que el objetivo actual es mayor que el objetivo más cercano , actualice el objetivo más cercano y reinicie el resultado de arrayList [] en una nueva lista.
- Repita la lista de ID cuya clave es currentTarget y agregue todas las combinaciones posibles de pares de ID en la lista de resultados .
- Después de completar los pasos anteriores, imprima todos los pares de ID almacenados en ArrayList result[] .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find pairs of ids with
// sum of values closest to the target
// but not exceeding the target
public static void closestPair(
int[][] arr1, int[][] arr2, int target)
{
// Initialize TreeMap having array
// element value as key and list of
// ids as value in the TreeMap
TreeMap<Integer, List<Integer> > valueToIds
= new TreeMap<>();
// list to store all answer pairs
List<int[]> result = new ArrayList<>();
// Keeps the track of maximum sum
// of pair values not exceeding target
int closestTarget = 0;
// Iterate through the array arr1 and
// add all elements in the TreeMap
for (int[] a : arr1) {
int val = a[1], id = a[0];
valueToIds.putIfAbsent(
val, new ArrayList<>());
valueToIds.get(val).add(id);
}
for (int[] b : arr2) {
// Find the corresponding value
// to be found
int remaining = target - b[1];
if (remaining < 0)
continue;
// Find a value which is close to
// desired value, not exceeding it
Integer floor = valueToIds.floorKey(
remaining);
// No value found which is less
// than or equal to floor
if (floor == null)
continue;
int currentTarget = b[1] + floor;
if (currentTarget >= closestTarget) {
if (currentTarget > closestTarget) {
// Update closeTarget and reset
// result list
closestTarget = currentTarget;
result = new ArrayList<>();
}
// Add all possible pairs in
// result list
for (int id : valueToIds.get(floor))
result.add(
new int[] { id, b[0] });
}
}
// Print all the id pairs
for (int[] ans : result) {
System.out.println(
ans[0] + " " + ans[1]);
}
}
// Driver Code
public static void main(String[] args)
{
int[][] arr1
= { { 1, 2000 }, { 2, 3000 }, { 3, 2000 } };
int[][] arr2 = { { 1, 3000 },
{ 2, 3000 } };
int target = 5500;
closestPair(arr1, arr2, target);
}
}
1 1 3 1 1 2 3 2
Complejidad de tiempo: O(N*log N + M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por darkphoenix349 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA