Dada una array de enteros arr[] y un entero positivo K , la tarea es contar todos los pares distintos con diferencias iguales a K.
Ejemplos:
Entrada: arr[ ] = {1, 5, 3, 4, 2}, K = 3
Salida: 2
Explicación: Hay 2 pares distintos con diferencia 3, los pares son {1, 4} y {5, 2}Entrada: arr[] = {8, 12, 16, 4, 0, 20}, K = 4
Salida: 5
Explicación: Hay 5 pares únicos con diferencia 4.
Los pares son {0, 4}, {4, 8 }, {8, 12}, {12, 16} y {16, 20}
El enfoque ingenuo y el enfoque basado en la clasificación y la búsqueda binaria se mencionan en el Conjunto 1 de este artículo.
Enfoque: la complejidad temporal de este problema se puede reducir para que tenga una complejidad lineal en el caso promedio mediante el uso de hashing con la ayuda de mapas desordenados según la siguiente idea:
Para formar tales pares únicos, si se atraviesa desde el elemento más pequeño, un elemento (por ejemplo, x ) formará tal par con otro elemento que tenga valor (x+K) .
Cuando la diferencia K = 0, los elementos que tengan una frecuencia superior a 1 podrán formar pares consigo mismos.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Inicialice un mapa desordenado e inserte todos los elementos de la array en el mapa.
- Si el valor dado de K es 0 :
- Si la frecuencia del elemento actual x es mayor que 1, incremente la cuenta en 1.
- De lo contrario, intente lo mismo con los demás elementos.
- Si el valor dado de K no es 0:
- Busque x + K en el mapa y si lo encuentra, incremente el conteo en 1.
- De lo contrario, intente con los otros elementos.
- Devuelve la cuenta .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to find total pairs
int TotalPairs(vector<int> nums, int K)
{
// Initializing a map
unordered_map<int, int> mp;
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
mp[nums[i]]++;
}
// Difference equal to zero
if (K == 0) {
for (auto i : mp) {
// Frequency of element is
// greater than one then
// distinct pair is possible
if (i.second > 1)
cnt++;
}
}
// Difference is not equal to zero
else {
for (auto i : mp) {
// Frequency of element + k
// is not zero then distinct
// pair is possible
if (mp.find(i.first + K)
!= mp.end()) {
cnt++;
}
}
}
return cnt;
}
// Driver Code
int main()
{
vector<int> arr = { 8, 12, 16, 4, 0, 20 };
int K = 4;
// Function call
int ans = TotalPairs(arr, K);
cout << ans;
return 0;
}
Java
// Java code to implement the above approach.
import java.io.*;
import java.util.*;
class GFG {
// Function to find total pairs
public static int TotalPairs(int nums[], int K)
{
// Initializing a map
Map<Integer, Integer> mp
= new HashMap<Integer, Integer>();
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (mp.get(nums[i]) != null)
mp.put(nums[i], mp.get(nums[i]) + 1);
else
mp.put(nums[i], 1);
}
// Difference equal to zero
if (K == 0) {
for (Map.Entry<Integer, Integer> it :
mp.entrySet()) {
// Frequency of element is
// greater than one then
// distinct pair is possible
if (it.getValue() > 1)
cnt++;
}
}
// Difference is not equal to zero
else {
for (Map.Entry<Integer, Integer> it :
mp.entrySet()) {
// Frequency of element + k
// is not zero then distinct
// pair is possible
if (mp.get(it.getKey() + K) != null) {
cnt++;
}
}
}
return cnt;
}
public static void main(String[] args)
{
int arr[] = { 8, 12, 16, 4, 0, 20 };
int K = 4;
// Function call
int ans = TotalPairs(arr, K);
System.out.print(ans);
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python3 program for above approach # function to find total pairs def TotalPairs(nums, K): # Initializing a map or dictionary mp = dict() cnt = 0 for i in range(len(nums)): if nums[i] in mp: mp[nums[i]] += 1 else: mp[nums[i]] = 1 # Difference equal to zero if K == 0: for i in mp: # Frequency of element is # greater than one then # distinct pair is possible if mp[i] > 1: cnt += 1 # Difference is not equal to zero else: for i in mp: # Frequency of element + k # is not zero then distinct #pair is possible if i + K in mp: cnt += 1 return cnt # Driver Code arr = [8, 12, 16, 4, 0, 20] K = 4 # Function call ans = TotalPairs(arr, K) print(ans) # This code is contributed by phasing17
C#
// C# code to implement the above approach.
using System;
using System.Collections.Generic;
public class GFG {
public static int TotalPairs(int[] nums, int K)
{
// Initializing a map
Dictionary<int, int> mp
= new Dictionary<int, int>();
int cnt = 0;
for (int i = 0; i < nums.Length; i++) {
if (mp.ContainsKey(nums[i]))
mp[nums[i]] += 1;
else
mp[nums[i]] = 1;
}
// Difference equal to zero
if (K == 0) {
foreach(KeyValuePair<int, int> it in mp)
{
// Frequency of element is
// greater than one then
// distinct pair is possible
if (it.Value > 1)
cnt++;
}
}
// Difference is not equal to zero
else {
foreach(KeyValuePair<int, int> it in mp)
{
// Frequency of element + k
// is not zero then distinct
// pair is possible
if (mp.ContainsKey(it.Key + K)) {
cnt++;
}
}
}
return cnt;
}
public static void Main(string[] args)
{
int[] arr = { 8, 12, 16, 4, 0, 20 };
int K = 4;
// Function call
int ans = TotalPairs(arr, K);
Console.Write(ans);
}
}
// This code is contributed by phasing17
Javascript
<script>// JavaScript program for the above approach
// function to find total pairs
function TotalPairs(nums, K)
{
// Initializing a map or dictionary
var mp = {};
var cnt = 0;
for (var i = 0; i < nums.length; i++) {
if (mp.hasOwnProperty(nums[i]))
mp[nums[i]] += 1;
else
mp[nums[i]] = 1;
}
// Difference equal to zero
if (K == 0) {
for (const i of Object.keys(mp)) {
// Frequency of element is
// greater than one then
// distinct pair is possible
console.log(i, mp[i], cnt);
if (mp[i] > 1)
cnt += 1;
}
}
// Difference is not equal to zero
else {
for (const i of Object.keys(mp)) {
// Frequency of element + k
// is not zero then distinct
// pair is possible\
if (mp.hasOwnProperty(parseInt(i) + K))
{
cnt += 1;
}
}
}
return cnt;
}
// Driver Code
var arr = [ 8, 12, 16, 4, 0, 20 ];
var K = 4;
// Function call
// var ans = TotalPairs(arr, K);
document.write(TotalPairs(arr, K));
// This code is contributed by phasing17
</script>
5
Complejidad de tiempo: O(N) [En el caso promedio, porque la complejidad de tiempo del caso promedio del mapa desordenado es O(1)]
Espacio auxiliar: O(N)