Auxil Dada una array 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:
Input : arr[] = {1, 1, 2} Output : 1 As arr[0] = arr[1], the pair of indices is (0, 1) Input : arr[] = {1, 1, 1} Output : 3 As arr[0] = arr[1], the pair of indices is (0, 1), (0, 2) and (1, 2) Input : arr[] = {1, 2, 3} Output : 0
Método 1 (Fuerza bruta): para cada índice i, busque el elemento después de él con el mismo valor que arr[i]. A continuación se muestra la implementación de este enfoque:
Implementación:
C++
// C++ program to count of pairs with equal // elements in an array. #include<bits/stdc++.h> using namespace std; // Return the number of pairs with equal // values. int countPairs(int arr[], int n) { int ans = 0; // for each index i and j for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driven Program int main() { int arr[] = { 1, 1, 2 }; int n = sizeof(arr)/sizeof(arr[0]); cout << countPairs(arr, n) << endl; return 0; }
Java
// Java program to count of pairs with equal // elements in an array. class GFG { // Return the number of pairs with equal // values. static int countPairs(int arr[], int n) { int ans = 0; // for each index i and j for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } //driver code public static void main (String[] args) { int arr[] = { 1, 1, 2 }; int n = arr.length; System.out.println(countPairs(arr, n)); } } // This code is contributed by Anant Agarwal.
Python3
# Python3 program to # count of pairs with equal # elements in an array. # Return the number of # pairs with equal values. def countPairs(arr, n): ans = 0 # for each index i and j for i in range(0 , n): for j in range(i + 1, n): # finding the index # with same value but # different index. if (arr[i] == arr[j]): ans += 1 return ans # Driven Code arr = [1, 1, 2 ] n = len(arr) print(countPairs(arr, n)) # This code is contributed # by Smitha
C#
// C# program to count of pairs with equal // elements in an array. using System; class GFG { // Return the number of pairs with equal // values. static int countPairs(int []arr, int n) { int ans = 0; // for each index i and j for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driver code public static void Main () { int []arr = { 1, 1, 2 }; int n = arr.Length; Console.WriteLine(countPairs(arr, n)); } } // This code is contributed by anuj_67.
PHP
<?php // PHP program to count of // pairs with equal elements // in an array. // Return the number of pairs // with equal values. function countPairs( $arr, $n) { $ans = 0; // for each index i and j for ( $i = 0; $i < $n; $i++) for ( $j = $i + 1; $j < $n; $j++) // finding the index with same // value but different index. if ($arr[$i] == $arr[$j]) $ans++; return $ans; } // Driven Code $arr = array( 1, 1, 2 ); $n = count($arr); echo countPairs($arr, $n) ; // This code is contributed by anuj_67. ?>
Javascript
<script> // Javascript program to count of pairs with equal // elements in an array. // Return the number of pairs with equal // values. function countPairs(arr, n) { let ans = 0; // for each index i and j for (let i = 0; i < n; i++) for (let j = i+1; j < n; j++) // finding the index with same // value but different index. if (arr[i] == arr[j]) ans++; return ans; } // Driver code let arr = [ 1, 1, 2 ]; let n = arr.length; document.write(countPairs(arr, n)); // This code is contributed by susmitakundugoaldanga. </script>
1
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (enfoque eficiente):
La idea es contar la frecuencia de cada número y luego encontrar el número de pares con elementos iguales. Supongamos que un número x aparece k veces en el índice i 1 , i 2 ,….,i k . Luego elija dos índices i x e i y que se contarán como 1 par. Del mismo modo, i y e i x también pueden ser pares. Entonces, elija n C 2 es el número de pares tal que arr[i] = arr[j] = x.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to count of index pairs with // equal elements in an array. #include<bits/stdc++.h> using namespace std; // Return the number of pairs with equal // values. int countPairs(int arr[], int n) { unordered_map<int, int> mp; // Finding frequency of each number. for (int i = 0; i < n; i++) mp[arr[i]]++; // Calculating pairs of each value. int ans = 0; for (auto it=mp.begin(); it!=mp.end(); it++) { int count = it->second; ans += (count * (count - 1))/2; } return ans; } // Driven Program int main() { int arr[] = {1, 1, 2}; int n = sizeof(arr)/sizeof(arr[0]); cout << countPairs(arr, n) << endl; return 0; }
Java
// Java program to count of index pairs with // equal elements in an array. import java.util.*; class GFG { public static int countPairs(int arr[], int n) { //A method to return number of pairs with // equal values HashMap<Integer,Integer> hm = new HashMap<>(); // Finding frequency of each number. for(int i = 0; i < n; i++) { if(hm.containsKey(arr[i])) hm.put(arr[i],hm.get(arr[i]) + 1); else hm.put(arr[i], 1); } int ans=0; // Calculating count of pairs with equal values for(Map.Entry<Integer,Integer> it : hm.entrySet()) { int count = it.getValue(); ans += (count * (count - 1)) / 2; } return ans; } // Driver code public static void main(String[] args) { int arr[] = new int[]{1, 2, 3, 1}; System.out.println(countPairs(arr,arr.length)); } } // This Code is Contributed // by Adarsh_Verma
Python3
# Python3 program to count of index pairs # with equal elements in an array. import math as mt # Return the number of pairs with # equal values. def countPairs(arr, n): mp = dict() # Finding frequency of each number. for i in range(n): if arr[i] in mp.keys(): mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Calculating pairs of each value. ans = 0 for it in mp: count = mp[it] ans += (count * (count - 1)) // 2 return ans # Driver Code arr = [1, 1, 2] n = len(arr) print(countPairs(arr, n)) # This code is contributed by mohit kumar 29
C#
// C# program to count of index pairs with // equal elements in an array. using System; using System.Collections.Generic; class GFG { // Return the number of pairs with // equal values. public static int countPairs(int []arr, int n) { // A method to return number of pairs // with equal values Dictionary<int, int> hm = new Dictionary<int, int>(); // Finding frequency of each number. for(int i = 0; i < n; i++) { if(hm.ContainsKey(arr[i])) { int a = hm[arr[i]]; hm.Remove(arr[i]); hm.Add(arr[i], a + 1); } else hm.Add(arr[i], 1); } int ans = 0; // Calculating count of pairs with // equal values foreach(var it in hm) { int count = it.Value; ans += (count * (count - 1)) / 2; } return ans; } // Driver code public static void Main() { int []arr = new int[]{1, 2, 3, 1}; Console.WriteLine(countPairs(arr,arr.Length)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to count of index pairs with // equal elements in an array. function countPairs(arr,n) { //A method to return number of pairs with // equal values let hm = new Map(); // Finding frequency of each number. for(let i = 0; i < n; i++) { if(hm.has(arr[i])) hm.set(arr[i],hm.get(arr[i]) + 1); else hm.set(arr[i], 1); } let ans=0; // Calculating count of pairs with equal values for(let [key, value] of hm.entries()) { let count = value; ans += (count * (count - 1)) / 2; } return ans; } // Driver code let arr=[1, 2, 3, 1]; document.write(countPairs(arr,arr.length)); // This code is contributed by patel2127 </script>
1
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar 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