Dados dos arreglos de enteros arr[] y brr[] que consisten en elementos distintos de tamaño N y M respectivamente y un entero K , la tarea es encontrar el conteo de pares (arr[i] , brr[j]) tal que (brr [j] – arr[i]) > K.
Ejemplos:
Entrada: arr[] = {5, 9, 1, 8}, brr[] = {10, 12, 7, 4, 2, 3}, K = 3
Salida: 6
Explicación:
Los posibles pares que satisfacen las condiciones dadas son : {(5, 10), (5, 12), (1, 10), (1, 12), (1, 7), (8, 12)}.
Por lo tanto, la salida requerida es 6.Entrada: arr[] = {2, 10}, brr[] = {5, 7}, K = 2
Salida: 2
Explicación:
Los posibles pares que satisfacen las condiciones dadas son: {(2, 5), (2, 7 )}.
Por lo tanto, la salida requerida es 2.
Enfoque ingenuo: consulte la publicación anterior de este artículo para conocer el enfoque más simple para resolver este problema.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Enfoque de dos punteros : consulte la publicación anterior de este artículo para ver la solución de dos punteros a este problema.
Complejidad de tiempo: O(N * log(N) + M * log(M))
Espacio auxiliar: O(1)
Enfoque eficiente: la idea es ordenar la array más pequeña y atravesar la array más grande para cada elemento, encontrar el elemento apropiado en la array más pequeña para emparejar mediante la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice una cuenta variable para almacenar la cuenta de pares.
- Si el tamaño de arr[] es más pequeño que brr[] , haga lo siguiente.
- Ordene la array arr[] y recorra la array brr[].
- Encuentre el límite inferior de (brr[j] – k) en arr[] ya que los números que son menores que brr[j] – k en arr[] se emparejarán perfectamente con brr[j].
- Agregue el índice de límite inferior con el conteo.
- Si el tamaño de brr[] es más pequeño que arr[] , haga lo siguiente.
- Ordene la array brr[] y recorra arr[] .
- Encuentre el límite superior de (arr[i] + k) en brr[] ya que los números que son mayores que arr[i]+k en brr[] se emparejarán perfectamente con arr[i].
- Agregue (Tamaño de brr[] – índice de límite superior) con el conteo.
- Después de los pasos anteriores, imprima el valor de count como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count pairs that satisfy
// the given conditions
int countPairs(int v1[], int v2[],
int n, int m, int k)
{
// Stores the count of pairs
int count = 0;
// If v1[] is smaller than v2[]
if (n <= m) {
// Sort the array v1[]
sort(v1, v1 + n);
// Traverse the array v2[]
for (int j = 0; j < m; j++) {
// Returns the address of
// the first number which
// is >= v2[j] - k
int index
= lower_bound(v1, v1 + n,
v2[j] - k)
- v1;
// Increase the count by all
// numbers less than v2[j] - k
count += index;
}
}
// Otherwise
else {
// Sort the array v2[]
sort(v2, v2 + m);
// Traverse the array v1[]
for (int i = 0; i < n; i++) {
// Returns the address of
// the first number which
// is > v1[i] + k
int index
= upper_bound(v2, v2 + m,
v1[i] + k)
- v2;
// Increase the count by all
// numbers greater than v1[i] + k
count += m - index;
}
}
// Return the total count of pairs
return count;
}
// Driver Code
int main()
{
int arr[] = { 5, 9, 1, 8 };
int brr[] = { 10, 12, 7, 4, 2, 3 };
int K = 3;
int N = sizeof(arr)
/ sizeof(arr[0]);
int M = sizeof(brr)
/ sizeof(brr[0]);
cout << countPairs(arr, brr,
N, M, K);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to count pairs
// that satisfy the given
// conditions
static int countPairs(int v1[], int v2[],
int n, int m, int k)
{
// Stores the count of pairs
int count = 0;
// If v1[] is smaller than v2[]
if (n <= m)
{
// Sort the array v1[]
Arrays.sort(v1);
// Traverse the array v2[]
for (int j = 0; j < m; j++)
{
// Returns the address of
// the first number which
// is >= v2[j] - k
int index = lowerBound(v1, 0, n,
v2[j] - k);
// Increase the count by all
// numbers less than v2[j] - k
count += index;
}
}
// Otherwise
else
{
// Sort the array v2[]
Arrays.sort(v2);
// Traverse the array v1[]
for (int i = 0; i < n; i++)
{
// Returns the address of
// the first number which
// is > v1[i] + k
int index = upperBound(v2, 0, m,
v1[i] + k);
// Increase the count by all
// numbers greater than v1[i] + k
count += m - index;
}
}
// Return the total count of pairs
return count;
}
static int lowerBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upperBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {5, 9, 1, 8};
int brr[] = {10, 12, 7,
4, 2, 3};
int K = 3;
int N = arr.length;
int M = brr.length;
System.out.print(countPairs(arr, brr,
N, M, K));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect_right # Function to count pairs that satisfy # the given conditions def countPairs(v1, v2, n, m, k): # Stores the count of pairs count = 0 # If v1[] is smaller than v2[] if (n <= m): # Sort the array v1[] v1 = sorted(v1) # Traverse the array v2[] for j in range(m): # Returns the address of # the first number which # is >= v2[j] - k index = bisect_left(v1, v2[j] - k) # Increase the count by all # numbers less than v2[j] - k count += index # Otherwise else: # Sort the array v2[] v2 = sorted(v2) # Traverse the array v1[] for i in range(n): # Returns the address of # the first number which # is > v1[i] + k index = bisect_right(v2, v1[i] + k) # Increase the count by all # numbers greater than v1[i] + k count += m - index # Return the total count of pairs return count # Driver Code if __name__ == '__main__': arr = [ 5, 9, 1, 8 ] brr = [ 10, 12, 7, 4, 2, 3] K = 3 N = len(arr) M = len(brr) print(countPairs(arr, brr, N, M, K)) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to count pairs
// that satisfy the given
// conditions
static int countPairs(int []v1, int []v2,
int n, int m, int k)
{
// Stores the count of pairs
int count = 0;
// If v1[] is smaller than v2[]
if (n <= m)
{
// Sort the array v1[]
Array.Sort(v1);
// Traverse the array v2[]
for (int j = 0; j < m; j++)
{
// Returns the address of
// the first number which
// is >= v2[j] - k
int index = lowerBound(v1, 0, n,
v2[j] - k);
// Increase the count by all
// numbers less than v2[j] - k
count += index;
}
}
// Otherwise
else
{
// Sort the array v2[]
Array.Sort(v2);
// Traverse the array v1[]
for (int i = 0; i < n; i++)
{
// Returns the address of
// the first number which
// is > v1[i] + k
int index = upperBound(v2, 0, m,
v1[i] + k);
// Increase the count by all
// numbers greater than v1[i] + k
count += m - index;
}
}
// Return the total count
// of pairs
return count;
}
static int lowerBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int upperBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low +
(high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {5, 9, 1, 8};
int []brr = {10, 12, 7,
4, 2, 3};
int K = 3;
int N = arr.Length;
int M = brr.Length;
Console.Write(countPairs(arr, brr,
N, M, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to count pairs
// that satisfy the given
// conditions
function countPairs(v1, v2, n, m, k)
{
// Stores the count of pairs
let count = 0;
// If v1[] is smaller than v2[]
if (n <= m)
{
// Sort the array v1[]
v1.sort();
// Traverse the array v2[]
for (let j = 0; j < m; j++)
{
// Returns the address of
// the first number which
// is >= v2[j] - k
let index = lowerBound(v1, 0, n,
v2[j] - k);
// Increase the count by all
// numbers less than v2[j] - k
count += index;
}
}
// Otherwise
else
{
// Sort the array v2[]
v2.sort();
// Traverse the array v1[]
for (let i = 0; i < n; i++)
{
// Returns the address of
// the first number which
// is > v1[i] + k
let index = upperBound(v2, 0, m,
v1[i] + k);
// Increase the count by all
// numbers greater than v1[i] + k
count += m - index;
}
}
// Return the total count of pairs
return count;
}
function lowerBound(a, low,
high, element)
{
while(low < high)
{
let middle = low +
(high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
function upperBound(a, low,
high, element)
{
while(low < high)
{
let middle = low +
(high - low) / 2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
let arr = [5, 9, 1, 8];
let brr = [10, 12, 7,
4, 2, 3];
let K = 3;
let N = arr.length;
let M = brr.length;
document.write(countPairs(arr, brr,
N, M, K));
</script>
Producción:
6
Complejidad de tiempo: O((N+M) * min(log(N), log(M)))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por swapnoneelmajumdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA