Dada una array de n enteros, necesitamos encontrar todos los pares con una diferencia menor que k
Ejemplos:
Input : a[] = {1, 10, 4, 2}
K = 3
Output : 2
We can make only two pairs
with difference less than 3.
(1, 2) and (4, 2)
Input : a[] = {1, 8, 7}
K = 7
Output : 2
Pairs with difference less than 7
are (1, 7) and (8, 7)
Método 1 (Simple) : Ejecute dos bucles anidados. El bucle exterior recoge todos los elementos x uno por uno. El ciclo interno considera todos los elementos después de x y verifica si la diferencia está dentro de los límites o no.
Implementación:
C++
// CPP code to find count of Pairs with
// difference less than K.
#include <bits/stdc++.h>
using namespace std;
int countPairs(int a[], int n, int k)
{
int res = 0;
for (int i = 0; i < n; i++)
for (int j=i+1; j<n; j++)
if (abs(a[j] - a[i]) < k)
res++;
return res;
}
// Driver code
int main()
{
int a[] = {1, 10, 4, 2};
int k = 3;
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n, k) << endl;
return 0;
}
Java
// java code to find count of Pairs with
// difference less than K.
import java.io.*;
class GFG {
static int countPairs(int a[], int n, int k)
{
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (Math.abs(a[j] - a[i]) < k)
res++;
return res;
}
// Driver code
public static void main (String[] args)
{
int a[] = {1, 10, 4, 2};
int k = 3;
int n = a.length;
System.out.println(countPairs(a, n, k));
}
}
// This code is contributed by vt_m.
Python3
# Python3 code to find count of Pairs # with difference less than K. def countPairs(a, n, k): res = 0 for i in range(n): for j in range(i + 1, n): if (abs(a[j] - a[i]) < k): res += 1 return res # Driver code a = [1, 10, 4, 2] k = 3 n = len(a) print(countPairs(a, n, k), end = "") # This code is contributed by Azkia Anam.
C#
// C# code to find count of Pairs
// with difference less than K.
using System;
class GFG {
// Function to count pairs
static int countPairs(int []a, int n,
int k)
{
int res = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (Math.Abs(a[j] - a[i]) < k)
res++;
return res;
}
// Driver code
public static void Main ()
{
int []a = {1, 10, 4, 2};
int k = 3;
int n = a.Length;
Console.WriteLine(countPairs(a, n, k));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find count of Pairs
// with difference less than K.
function countPairs( $a, $n, $k)
{
$res = 0;
for($i = 0; $i < $n; $i++)
for($j = $i + 1; $j < $n; $j++)
if (abs($a[$j] - $a[$i]) < $k)
$res++;
return $res;
}
// Driver code
$a = array(1, 10, 4, 2);
$k = 3;
$n = count($a);
echo countPairs($a, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript code to find count of Pairs
// with difference less than K.
function countPairs(a, n, k)
{
var res = 0;
for(var i = 0; i < n; i++)
for(var j = i + 1; j < n; j++)
if (Math.abs(a[j] - a[i]) < k)
res++;
return res;
}
// Driver code
var a = [ 1, 10, 4, 2 ];
var k = 3;
var n = a.length;
document.write(countPairs(a, n, k));
// This code is contributed by bunnyram19
</script>
2
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (Ordenar): Primero ordenamos la array. Luego comenzamos desde el primer elemento y seguimos considerando pares mientras la diferencia sea menor que k. Si detenemos el ciclo cuando encontramos una diferencia mayor o igual a k y pasamos al siguiente elemento.
Implementación:
C++
// C++ code to find count of Pairs with
// difference less than K.
#include <bits/stdc++.h>
using namespace std;
int countPairs(int a[], int n, int k)
{
// to sort the array.
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; i++) {
// Keep incrementing result while
// subsequent elements are within
// limits.
int j = i+1;
while (j < n && a[j] - a[i] < k) {
res++;
j++;
}
}
return res;
}
// Driver code
int main()
{
int a[] = {1, 10, 4, 2};
int k = 3;
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n, k) << endl;
return 0;
}
Java
// Java code to find count of Pairs with
// difference less than K.
import java.io.*;
import java.util.Arrays;
class GFG
{
static int countPairs(int a[], int n, int k)
{
// to sort the array.
Arrays.sort(a);
int res = 0;
for (int i = 0; i < n; i++)
{
// Keep incrementing result while
// subsequent elements are within
// limits.
int j = i + 1;
while (j < n && a[j] - a[i] < k)
{
res++;
j++;
}
}
return res;
}
// Driver code
public static void main (String[] args)
{
int a[] = {1, 10, 4, 2};
int k = 3;
int n = a.length;
System.out.println(countPairs(a, n, k));
}
}
// This code is contributed by vt_m.
Python3
# Python code to find count of Pairs # with difference less than K. def countPairs(a, n, k): # to sort the array a.sort() res = 0 for i in range(n): # Keep incrementing result while # subsequent elements are within limits. j = i+1 while (j < n and a[j] - a[i] < k): res += 1 j += 1 return res # Driver code a = [1, 10, 4, 2] k = 3 n = len(a) print(countPairs(a, n, k), end = "") # This code is contributed by Azkia Anam.
C#
// C# code to find count of Pairs
// with difference less than K.
using System;
class GFG {
// Function to count pairs
static int countPairs(int []a, int n,
int k)
{
// to sort the array.
Array.Sort(a);
int res = 0;
for (int i = 0; i < n; i++)
{
// Keep incrementing result while
// subsequent elements are within
// limits.
int j = i + 1;
while (j < n && a[j] - a[i] < k)
{
res++;
j++;
}
}
return res;
}
// Driver code
public static void Main ()
{
int []a = {1, 10, 4, 2};
int k = 3;
int n = a.Length;
Console.WriteLine(countPairs(a, n, k));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find count of
// Pairs with difference less than K.
function countPairs( $a, $n, $k)
{
// to sort the array.
sort($a);
$res = 0;
for ( $i = 0; $i < $n; $i++)
{
// Keep incrementing result
// while subsequent elements
// are within limits.
$j = $i + 1;
while ($j < $n and
$a[$j] - $a[$i] < $k)
{
$res++;
$j++;
}
}
return $res;
}
// Driver code
$a = array(1, 10, 4, 2);
$k = 3;
$n = count($a);
echo countPairs($a, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript code to find count of Pairs with
// difference less than K.
function countPairs(a, n, k)
{
// To sort the array.
a.sort((a, b) => a - b);
let res = 0;
for(let i = 0; i < n; i++)
{
// Keep incrementing result while
// subsequent elements are within
// limits.
let j = i + 1;
while (j < n && a[j] - a[i] < k)
{
res++;
j++;
}
}
return res;
}
// Driver code
let a = [ 1, 10, 4, 2 ];
let k = 3;
let n = a.length;
document.write(countPairs(a, n, k) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
2
Complejidad de tiempo: O(res) donde res es el número de pares en la salida. Tenga en cuenta que, en el peor de los casos, esto también requiere un tiempo O(n 2 ) pero, en general, funciona mucho mejor.
Método 3 (Usando lower_bound):
El problema se puede resolver de manera eficiente utilizando la función lower_bound en complejidad de tiempo O(n*log(n)).
La idea es ordenar primero los elementos de la array y luego para cada elemento a[i], encontraremos todos los elementos que están en el lado derecho de a[i] y cuya diferencia con a[i] es menor que k . Esto se puede evaluar buscando todos los elementos que tengan un valor menor que a[i]+k. Y esto se puede evaluar fácilmente con la ayuda de la función lower_bound en tiempo O(log(n)) para cada elemento.
Ejemplo ilustrativo:
Dado: a[] = {1, 10, 4, 2} y k=3
Array después de ordenar: a[] = {1, 2, 4, 10}
Para 1, todos los elementos en el lado derecho de 1 que son menores que 1+3=4 -> {2}
Para 2, todos los elementos del lado derecho de 2 que son menores que 2+3=5 -> {4}
Para 4, todos los elementos del lado derecho de 4 que son menores que 4+ 3=7 -> {}
Para 10, todos los elementos en el lado derecho de 10 que son menores que 10+3=13 -> {}
Entonces encontramos un total de 2 de esos elementos, por lo tanto, respuesta = 2.
Acercarse:
- Ordenar la array dada.
- Iterar a través de cada elemento y almacenar a[i]+k en val para el índice i.
- Luego, usando la función lower_bound, encontraremos el índice de la primera aparición de elementos que es mayor o igual que val.
- Después de esto, agregaremos el conteo de todos los pares para a[i] al encontrar la diferencia entre el índice que se encuentra usando la función de límite inferior y el índice actual i.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to find count of Pairs with
// difference less than K.
#include <bits/stdc++.h>
using namespace std;
int countPairs(int a[], int n, int k)
{
// to sort the array.
sort(a, a + n);
int res = 0;
// iterating through each index
for (int i = 0; i < n; i++) {
// here val stores the value till
// which the number should be possible
// so that its difference with a[i]
// is less than k.
int val = a[i] + k;
// finding the first occurrence of
// element in array which is greater than
// or equal to val.
int y = lower_bound(a, a + n, val) - a;
// adding the count of all pairs
// possible for current a[i]
res += (y - i - 1);
}
return res;
}
// Driver code
int main()
{
int a[] = { 1, 10, 4, 2 };
int k = 3;
int n = sizeof(a) / sizeof(a[0]);
cout << countPairs(a, n, k) << endl;
return 0;
}
// This code is contributed by Pushpesh raj
2
Complejidad temporal: O(n*log(n))
Espacio auxiliar: O(1)
Este artículo es una contribución de Harsha Mogali . Si te gusta GeeksforGeeks y write.geeksforgeeks.org”>write.geeksforgeeks.org o envía tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA