Dada una array arr[] de N elementos. La tarea es contar el número total de índices (i, j) tales que arr[i] = arr[j] e i != j
Ejemplos:
Entrada : arr[]={1, 2, 1, 1}
Salida : 3
Explicación:
En la array arr[0]=arr[2]=arr[3]
Los pares válidos son (0, 2), (0, 3) ) y (2, 3)Entrada : arr[]={2, 2, 3, 2, 3}
Salida : 4
Explicación:
En la array arr[0]=arr[1]=arr[3] y arr[2]=arr[4]
Entonces Los pares válidos son (0, 1), (0, 3), (1, 3), (2, 4)
Para el enfoque ingenuo y eficiente, consulte la publicación anterior de este artículo.
Mejor enfoque: usar dos punteros: la idea es ordenar la array dada y la diferencia de índice que tiene los mismos elementos. A continuación se muestran los pasos:
- Ordenar la array dada.
- Inicialice los dos punteros izquierdo y derecho como 0 y 1 respectivamente.
- Ahora hasta que right sea menor que N , haga lo siguiente:
- Si el índice del elemento izquierdo y derecho es el mismo, incremente el puntero derecho y agregue la diferencia del puntero derecho e izquierdo al recuento final.
- De lo contrario, actualice el valor de izquierda a derecha.
- Imprima el valor de conteo después de los pasos anteriores.
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 that counts the pair in
// the array arr[]
int countPairs(int arr[], int n)
{
int ans = 0;
// Sort the array
sort(arr, arr + n);
// Initialize two pointers
int left = 0, right = 1;
while (right < n) {
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 2, 3, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that counts the pair in
// the array arr[]
static int countPairs(int arr[], int n)
{
int ans = 0;
// Sort the array
Arrays.sort(arr);
// Initialize two pointers
int left = 0, right = 1;
while (right < n)
{
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 2, 3, 2, 3 };
int N = arr.length;
// Function call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # Function that counts the pair in # the array arr[] def countPairs(arr, n): ans = 0 # Sort the array arr.sort() # Initialize two pointers left = 0 right = 1; while (right < n): if (arr[left] == arr[right]): # Add all valid pairs to answer ans += right - left; else: left = right; right += 1 # Return the answer return ans # Driver Code if __name__ == "__main__": # Given array arr[] arr = [2, 2, 3, 2, 3] N = len(arr) # Function call print (countPairs(arr, N)) # This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function that counts the pair in
// the array []arr
static int countPairs(int []arr, int n)
{
int ans = 0;
// Sort the array
Array.Sort(arr);
// Initialize two pointers
int left = 0, right = 1;
while (right < n)
{
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 2, 2, 3, 2, 3 };
int N = arr.Length;
// Function call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program for the above approach
// Function that counts the pair in
// the array arr[]
function countPairs(arr, n)
{
let ans = 0;
// Sort the array
arr.sort(function(a, b){return a - b});
// Initialize two pointers
let left = 0, right = 1;
while (right < n)
{
if (arr[left] == arr[right])
// Add all valid pairs to answer
ans += right - left;
else
left = right;
right++;
}
// Return the answer
return ans;
}
// Given array []arr
let arr = [ 2, 2, 3, 2, 3 ];
let N = arr.length;
// Function call
document.write(countPairs(arr, N));
</script>
Producción:
4
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Enfoque Eficiente – usando Traversal único: La idea es usar Hashing y actualizar el conteo de cada par cuya frecuencia es mayor a 1. A continuación se muestran los pasos:
- Cree un mapa_desordenado M para almacenar la frecuencia de cada elemento en la array .
- Recorra la array dada y siga actualizando la frecuencia de cada elemento en M .
- Mientras actualiza la frecuencia en el paso anterior, si la frecuencia de cualquier elemento es mayor que 0, cuente esa frecuencia hasta el recuento final.
- Imprima el conteo de pares después de los pasos anteriores.
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 that count the pairs having
// same elements in the array arr[]
int countPairs(int arr[], int n)
{
int ans = 0;
// Hash map to keep track of
// occurrences of elements
unordered_map<int, int> count;
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Check if occurrence of arr[i] > 0
// add count[arr[i]] to answer
if (count[arr[i]] != 0)
ans += count[arr[i]];
// Increase count of arr[i]
count[arr[i]]++;
}
// Return the result
return ans;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 1, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << countPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that count the pairs having
// same elements in the array arr[]
static int countPairs(int arr[], int n)
{
int ans = 0;
// Hash map to keep track of
// occurrences of elements
HashMap<Integer,
Integer> count = new HashMap<>();
// Traverse the array arr[]
for (int i = 0; i < n; i++)
{
// Check if occurrence of arr[i] > 0
// add count[arr[i]] to answer
if(count.containsKey(arr[i]))
{
ans += count.get(arr[i]);
count.put(arr[i], count.get(arr[i]) + 1);
}
else
{
count.put(arr[i], 1);
}
}
// Return the result
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 1, 1 };
int N = arr.length;
// Function call
System.out.print(countPairs(arr, N));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program for the above approach
# Function that count the pairs having
# same elements in the array arr[]
def countPairs(arr, n) :
ans = 0
# Hash map to keep track of
# occurrences of elements
count = {}
# Traverse the array arr[]
for i in range(n) :
# Check if occurrence of arr[i] > 0
# add count[arr[i]] to answer
if arr[i] in count :
ans += count[arr[i]]
# Increase count of arr[i]
if arr[i] in count :
count[arr[i]] += 1
else :
count[arr[i]] = 1
# Return the result
return ans
# Given array arr[]
arr = [ 1, 2, 1, 1 ]
N = len(arr)
# Function call
print(countPairs(arr, N))
# This code is contributed by divyesh072019
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that count the pairs having
// same elements in the array []arr
static int countPairs(int []arr, int n)
{
int ans = 0;
// Hash map to keep track of
// occurrences of elements
Dictionary<int,
int> count = new Dictionary<int,
int>();
// Traverse the array []arr
for (int i = 0; i < n; i++)
{
// Check if occurrence of arr[i] > 0
// add count[arr[i]] to answer
if(count.ContainsKey(arr[i]))
{
ans += count[arr[i]];
count[arr[i]] = count[arr[i]] + 1;
}
else
{
count.Add(arr[i], 1);
}
}
// Return the result
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 1, 2, 1, 1 };
int N = arr.Length;
// Function call
Console.Write(countPairs(arr, N));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program for the above approach
// Function that count the pairs having
// same elements in the array arr[]
function countPairs(arr, n)
{
let ans = 0;
// Hash map to keep track of
// occurrences of elements
let count = new Map();
// Traverse the array arr[]
for(let i = 0; i < n; i++)
{
// Check if occurrence of arr[i] > 0
// add count[arr[i]] to answer
if (count.has(arr[i]))
{
ans += count.get(arr[i]);
count.set(arr[i], count.get(arr[i]) + 1);
}
else
{
count.set(arr[i], 1);
}
}
// Return the result
return ans;
}
// Driver Code
let arr = [ 1, 2, 1, 1 ];
let N = arr.length;
// Function call
document.write(countPairs(arr, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pankajsharma_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA