Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar el número K de la array del producto.
Nota: Una array de productos prod[] de una array es una array ordenada de tamaño (N*(N-1))/2 en la que cada elemento se forma como prod[k] = arr[i] * arr[j] , donde 0 ≤ yo < j < norte .
Ejemplos:
Entrada: arr[] = {-4, -2, 3, 3}, K = 3
Salida: -6
Final prod[] array = {-12, -12, -6, -6, 8, 9}
donde prod [K] = -6
Entrada: arr[] = {5, 4, 3, 2, -1, 0, 0}, K = 20
Salida: 15
Enfoque ingenuo: Genere la array prod[] iterando la array dada dos veces y luego ordene la array prod[] y encuentre el K -ésimo elemento de la array.
Complejidad de tiempo: O(N 2 * log(N))
Enfoque eficiente: el número de pares negativos, cero y positivos se puede determinar fácilmente, por lo que puede saber si la respuesta es negativa, cero o positiva. Si la respuesta es negativa, es posible medir el número de pares que son mayores o iguales a K seleccionando uno a uno un número negativo y un número positivo, por lo que la respuesta se obtiene mediante una búsqueda binaria. La respuesta es exactamente la misma cuando la respuesta es positiva, pero considera elegir el mismo elemento dos veces y restarlo contará cada par exactamente dos veces.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Kth number in the list formed
// from product of any two numbers
// in the array and sorting them
#include <bits/stdc++.h>
using namespace std;
// Function to find number of pairs
bool check(long long x,
vector<int>& pos,
vector<int>& neg, int k)
{
long long pairs = 0;
int p = neg.size() - 1;
int nn = neg.size() - 1;
int pp = pos.size() - 1;
// Negative and Negative
for (int i = 0; i < neg.size(); i++) {
while (p >= 0 and neg[i] * neg[p] <= x)
p--;
// Add Possible Pairs
pairs += min(nn - p, nn - i);
}
// Positive and Positive
p = 0;
for (int i = pos.size() - 1; i >= 0; i--) {
while (p < pos.size() and pos[i] * pos[p] <= x)
p++;
// Add Possible pairs
pairs += min(p, i);
}
// Negative and Positive
p = pos.size() - 1;
for (int i = neg.size() - 1;
i >= 0;
i--) {
while (p >= 0 and neg[i] * pos[p] <= x)
p--;
// Add Possible pairs
pairs += pp - p;
}
return (pairs >= k);
}
// Function to find the kth
// element in the list
long long kth_element(int a[],
int n, int k)
{
vector<int> pos, neg;
// Separate Positive and
// Negative elements
for (int i = 0; i < n; i++) {
if (a[i] >= 0)
pos.push_back(a[i]);
else
neg.push_back(a[i]);
}
// Sort the Elements
sort(pos.begin(), pos.end());
sort(neg.begin(), neg.end());
long long l = -1e18,
ans = 0, r = 1e18;
// Binary search
while (l <= r) {
long long mid = (l + r) >> 1;
if (check(mid, pos, neg, k)) {
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
int a[] = { -4, -2, 3, 3 }, k = 3;
int n = sizeof(a) / sizeof(a[0]);
// Function call
cout << kth_element(a, n, k);
return 0;
}
Java
// Java implementation to find the
// Kth number in the list formed
// from product of any two numbers
// in the array and sorting them
import java.util.*;
class GFG
{
// Function to find number of pairs
static boolean check(int x, Vector pos, Vector neg, int k)
{
int pairs = 0;
int p = neg.size() - 1;
int nn = neg.size() - 1;
int pp = pos.size() - 1;
// Negative and Negative
for (int i = 0; i < neg.size(); i++)
{
while ((p >= 0) && ((int)neg.get(i) *
(int)neg.get(p) <= x))
p--;
// Add Possible Pairs
pairs += Math.min(nn - p, nn - i);
}
// Positive and Positive
p = 0;
for (int i = pos.size() - 1; i >= 0; i--)
{
while ((p < pos.size()) && ((int)pos.get(i) *
(int)pos.get(p) <= x))
p++;
// Add Possible pairs
pairs += Math.min(p, i);
}
// Negative and Positive
p = pos.size() - 1;
for (int i = neg.size() - 1;
i >= 0; i--) {
while ((p >= 0) && ((int)neg.get(i) *
(int)pos.get(p) <= x))
p--;
// Add Possible pairs
pairs += pp - p;
}
return (pairs >= k);
}
// Function to find the kth
// element in the list
static int kth_element(int a[], int n, int k)
{
Vector pos = new Vector();
Vector neg = new Vector();;
// Separate Positive and
// Negative elements
for (int i = 0; i < n; i++)
{
if (a[i] >= 0)
pos.add(a[i]);
else
neg.add(a[i]);
}
// Sort the Elements
//sort(pos.begin(), pos.end());
//sort(neg.begin(), neg.end());
Collections.sort(pos);
Collections.sort(neg);
int l = (int)-1e8, ans = 0, r = (int)1e8;
// Binary search
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid, pos, neg, k))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
// Return the required answer
return ans;
}
// Driver code
public static void main (String[] args)
{
int a[] = { -4, -2, 3, 3 }, k = 3;
int n = a.length;
// Function call
System.out.println(kth_element(a, n, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation to find the # Kth number in the list formed # from product of any two numbers # in the array and sorting them # Function to find number of pairs def check(x, pos, neg, k): pairs = 0 p = len(neg) - 1 nn = len(neg) - 1 pp = len(pos) - 1 # Negative and Negative for i in range(len(neg)): while (p >= 0 and neg[i] * neg[p] <= x): p -= 1 # Add Possible Pairs pairs += min(nn - p, nn - i) # Positive and Positive p = 0 for i in range(len(pos) - 1, -1, -1): while (p < len(pos) and pos[i] * pos[p] <= x): p += 1 # Add Possible pairs pairs += min(p, i) # Negative and Positive p = len(pos) - 1 for i in range(len(neg) - 1, -1, -1): while (p >= 0 and neg[i] * pos[p] <= x): p -= 1 # Add Possible pairs pairs += pp - p return (pairs >= k) # Function to find the kth # element in the list def kth_element(a, n, k): pos, neg = [],[] # Separate Positive and # Negative elements for i in range(n): if (a[i] >= 0): pos.append(a[i]) else: neg.append(a[i]) # Sort the Elements pos = sorted(pos) neg = sorted(neg) l = -10**18 ans = 0 r = 10**18 # Binary search while (l <= r): mid = (l + r) >> 1 if (check(mid, pos, neg, k)): ans = mid r = mid - 1 else: l = mid + 1 # Return the required answer return ans # Driver code a = [-4, -2, 3, 3] k = 3 n = len(a) # Function call print(kth_element(a, n, k)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// Kth number in the list formed
// from product of any two numbers
// in the array and sorting them
using System;
using System.Collections.Generic;
class GFG
{
// Function to find number of pairs
static bool check(int x, List<int> pos, List<int> neg, int k)
{
int pairs = 0;
int p = neg.Count - 1;
int nn = neg.Count - 1;
int pp = pos.Count - 1;
// Negative and Negative
for (int i = 0; i < neg.Count; i++)
{
while ((p >= 0) && ((int)neg[i] *
(int)neg[p] <= x))
p--;
// Add Possible Pairs
pairs += Math.Min(nn - p, nn - i);
}
// Positive and Positive
p = 0;
for (int i = pos.Count - 1; i >= 0; i--)
{
while ((p < pos.Count) && ((int)pos[i] *
(int)pos[p] <= x))
p++;
// Add Possible pairs
pairs += Math.Min(p, i);
}
// Negative and Positive
p = pos.Count - 1;
for (int i = neg.Count - 1; i >= 0; i--)
{
while ((p >= 0) && ((int)neg[i] *
(int)pos[p] <= x))
p--;
// Add Possible pairs
pairs += pp - p;
}
return (pairs >= k);
}
// Function to find the kth
// element in the list
static int kth_element(int []a, int n, int k)
{
List<int> pos = new List<int>();
List<int> neg = new List<int>();;
// Separate Positive and
// Negative elements
for (int i = 0; i < n; i++)
{
if (a[i] >= 0)
pos.Add(a[i]);
else
neg.Add(a[i]);
}
// Sort the Elements
//sort(pos.begin(), pos.end());
//sort(neg.begin(), neg.end());
pos.Sort();
neg.Sort();
int l = (int)-1e8, ans = 0, r = (int)1e8;
// Binary search
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid, pos, neg, k))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
// Return the required answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []a = { -4, -2, 3, 3 };
int k = 3;
int n = a.Length;
// Function call
Console.WriteLine(kth_element(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find the
// Kth number in the list formed
// from product of any two numbers
// in the array and sorting them
// Function to find number of pairs
function check(x, pos, neg, k)
{
let pairs = 0;
let p = neg.length - 1;
let nn = neg.length - 1;
let pp = pos.length - 1;
// Negative and Negative
for (let i = 0; i < neg.length; i++)
{
while ((p >= 0) && (neg[i] * neg[p] <= x))
p--;
// Add Possible Pairs
pairs += Math.min(nn - p, nn - i);
}
// Positive and Positive
p = 0;
for (let i = pos.length - 1; i >= 0; i--)
{
while ((p < pos.length) && (pos[i] * pos[p] <= x))
p++;
// Add Possible pairs
pairs += Math.min(p, i);
}
// Negative and Positive
p = pos.length - 1;
for (let i = neg.length - 1; i >= 0; i--)
{
while ((p >= 0) && (neg[i] * pos[p] <= x))
p--;
// Add Possible pairs
pairs += pp - p;
}
return (pairs >= k);
}
// Function to find the kth
// element in the list
function kth_element(a, n, k)
{
let pos = [];
let neg = [];
// Separate Positive and
// Negative elements
for (let i = 0; i < n; i++)
{
if (a[i] >= 0)
pos.push(a[i]);
else
neg.push(a[i]);
}
// Sort the Elements
//sort(pos.begin(), pos.end());
//sort(neg.begin(), neg.end());
pos.sort(function(a, b){return a - b});
neg.sort(function(a, b){return a - b});
let l = -1e8, ans = 0, r = 1e8;
// Binary search
while (l <= r)
{
let mid = (l + r) >> 1;
if (check(mid, pos, neg, k))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
// Return the required answer
return ans;
}
let a = [ -4, -2, 3, 3 ];
let k = 3;
let n = a.length;
// Function call
document.write(kth_element(a, n, k));
// This code is contributed by divyesh072019.
</script>
Producción:
-6
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA