Dadas dos arrays arr[] y brr[] que contienen números enteros. La tarea es encontrar el K -ésimo producto más grande de un par (arr[i], brr[j]) .
Ejemplos:
Entrada: arr[] = {1, -2, 3}, brr[] = {3, -4, 0}, K = 3
Salida: 3
Explicación: Todas las combinaciones de productos en orden descendente son: [9, 8, 3 , 0, 0, 0, -4, -6, -12] y el tercer elemento más grande es 3.Entrada: arr[] = {-1, -5, -3}, brr[] = {-3, -4, 0}, K =5
Salida: 4
Explicación: Todas las combinaciones de productos en orden descendente son: [20, 15, 12, 9, 4, 3, 0, 0, 0] y el quinto elemento más grande es 4.
Enfoque ingenuo: genere todas las combinaciones de productos posibles para cada elemento de la array arr[] con cada elemento de la array brr[] . Luego ordene la array de resultados y devuelva el elemento K-ésimo de la array de resultados.
C++
#include <bits/stdc++.h>
using namespace std;
int solve(int a[ ], int n, int b[ ], int m, int k) {
vector<int> ans;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// take product
int prod = a[i] * b[j];
ans.push_back(prod);
}
}
// Sort array in descending order
sort(ans.begin(), ans.end(), greater<int>());
// Finally return (k - 1)th index
// as indexing begin from 0.
return ans[k - 1];
}
// Driver code
int main()
{
int arr[ ] = { 1, -2, 3 };
int brr[ ] = { 3, -4, 0 };
int K = 3;
int n = sizeof(arr) / sizeof(int);
int m = sizeof(brr) / sizeof(int);
// Function Call
int val = solve(arr, n, brr, m, K);
cout << val;
return 0;
}
// This code is contributed by hrithikgarg03188
Java
// Java code for the above approach
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
class GFG {
static int solve(int[] a, int[] b, int k) {
List<Integer> ans = new LinkedList<>();
int n = a.length;
int m = b.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// take product
int prod = a[i] * b[j];
ans.add(prod);
}
}
// Sort array in descending order
Collections.sort(ans, (x, y) -> y - x);
// Finally return (k - 1)th index
// as indexing begins from 0.
return (ans.get(k - 1));
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, -2, 3 };
int[] brr = { 3, -4, 0 };
int K = 3;
// Function Call
int val = solve(arr, brr, K);
System.out.println(val);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for above approach def solve(a, b, k): ans = [] n = len(a) m = len(b) for i in range(n): for j in range(m): # take product prod = a[i]*b[j] ans.append(prod) # Sort array in descending order ans.sort(reverse = True) # Finally return (k-1)th index # as indexing begins from 0. return (ans[k-1]) # Driver Code arr = [1, -2, 3] brr = [3, -4, 0] K = 3 # Function Call val = solve(arr, brr, K) print(val)
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
public class GFG {
static int solve(int[] a, int[] b, int k) {
List<int> ans = new List<int>();
int n = a.Length;
int m = b.Length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// take product
int prod = a[i] * b[j];
ans.Add(prod);
}
}
// Sort array in descending order
ans.Sort((x, y) => y - x);
// Finally return (k - 1)th index
// as indexing begins from 0.
return (ans[k - 1]);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, -2, 3 };
int[] brr = { 3, -4, 0 };
int K = 3;
// Function Call
int val = solve(arr, brr, K);
Console.WriteLine(val);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript code for the above approach
function solve(a, b, k)
{
ans = []
n = a.length
m = b.length
for (let i = 0; i < n; i++)
{
for (let j = 0; j < m; j++)
{
// take product
prod = a[i] * b[j]
ans.push(prod)
}
}
// Sort array in descending order
ans.sort(function (a, b) { return b - a })
// Finally return (k - 1)th index
// as indexing begins from 0.
return (ans[k - 1])
}
// Driver Code
arr = [1, -2, 3]
brr = [3, -4, 0]
K = 3
// Function Call
val = solve(arr, brr, K)
document.write(val)
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de tiempo: O(N*M + (N+M) * Log(N+M))
Espacio auxiliar: O(N+M)
Enfoque eficiente: este problema se puede resolver utilizando el enfoque codicioso y montones . Siga los pasos a continuación para resolver el problema dado.
- Ordene la array brr[] .
- Mantenga una array de mayor tamaño en la array arr[] .
- Cree un montón máximo para almacenar los elementos con sus respectivos índices.
- Recorre cada elemento de la array arr[] . El elemento puede ser positivo o negativo.
- Positivo : multiplique el elemento actual de arr[] con el elemento más grande de la array ordenada brr[] . Para asegurar que se obtiene el máximo elemento.
- Negativo : en este caso, multiplique con el valor más pequeño , es decir, con el primer elemento de la array brr[] . Esto se debe a la propiedad de la negación, ya que se puede obtener un valor mayor al multiplicar por el menor.
- Inserte tres valores en el montón de modo que: (producto, i, j) donde i & j son los índices de las arrays arr[] y brr[] .
- Ahora ejecuta un bucle for K veces y extrae elementos del montón.
- Ahora compruebe si el valor presente en arr[i] es positivo o negativo
- Positivo : entonces next_j = (current_j – 1) porque como se ha utilizado el montón máximo, es posible que todos los índices más altos ya se hayan extraído del montón.
- Negativo : next_j = (current_j +1) porque todos los valores más pequeños que producen elementos más grandes podrían haber sido extraídos del montón.
- Finalmente, devuelve la respuesta.
Nota: Max heap se implementa con la ayuda de min-heap, negando los signos de los valores mientras los inserta en el montón en Python.
A continuación se muestra la implementación del enfoque anterior.
Python3
# Python program for above approach from heap import heappush as push, heappop as pop def solve(a, b, k): # Sorting array b in ascending order b.sort() n, m = len(a), len(b) # Checking if size(a) > size(b) if (n < m): # Otherwise swap the arrays return solve(b, a, k) heap = [] # Traverse all elements in array a for i in range(n): curr = a[i] # curr element is negative if (curr < 0): # Product with smallest value val = curr * b[0] # Pushing negative val due to max heap # and i as well jth index push(heap, (-val, i, 0)) else: # Product with largest value val = curr * b[-1] # Pushing negative val due to max heap # and i as well jth index push(heap, (-val, i, m-1)) # Subtract 1 due to zero indexing k = k-1 # Remove k-1 largest items from heap for _ in range(k): val, i, j = pop(heap) val = -val # if a[i] is negative, increment ith index if (a[i] < 0): next_j = j + 1 # if a[i] is positive, decrement jth index else: next_j = j-1 # if index is valid if (0 <= next_j < m): new_val = a[i] * b[next_j] # Pushing new_val in the heap push(heap, (-new_val, i, next_j)) # Finally return first val in the heap return -(heap[0][0]) # Driver Code arr = [1, -2, 3] brr = [3, -4, 0] K = 3 # Function Call val = solve(arr, brr, K) # Print the result print(val)
Producción:
3
Complejidad de tiempo: O(M*Log(M) + K*Log(N))
Espacio auxiliar: O(N)