Cuente todos los pares distintos de elementos repetidos de la array para cada elemento de la array

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros. Para cada elemento de la array, la tarea es contar los posibles pares (i, j), excluyendo el elemento actual, de modo que i < j y arr[i] = arr[j] .

Ejemplos:

Entrada: arr[] = {1, 1, 2, 1, 2}
Salida: 2 2 3 2 3
Explicación:
para el índice 1, los elementos restantes después de excluir el elemento actual son [1, 2, 1, 2]. Entonces, el conteo es 2.
Para el índice 2, los elementos restantes después de excluir el elemento en el índice 2 son [1, 2, 1, 2]. Entonces, el conteo es 2.
Para el índice 3, los elementos restantes después de excluir el elemento en el índice 3 son [1, 1, 1, 2]. Entonces, el conteo es 3.
Para el índice 4, los elementos restantes después de excluir el elemento en el índice 4 son [1, 1, 2, 2]. Entonces, el conteo es 2.
Para el índice 5, los elementos restantes después de excluir el elemento en el índice 5 son [1, 1, 2, 1. Entonces, el conteo es 3.

Entrada: arr[] = {1, 2, 3, 4}
Salida: 0 0 0 0
Explicación:
Dado que todos los elementos son distintos, no existe ningún par con el mismo valor.

Enfoque ingenuo: la idea ingenua es atravesar la array dada y, para cada elemento, excluir el elemento actual de la array y, con los elementos restantes de la array, encontrar todos los pares posibles (i, j) de modo que arr[i] sea igual a arr[ j] y yo < j . Imprime el conteo de pares para cada elemento. 
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es almacenar la frecuencia de cada elemento y contar todos los pares posibles (por ejemplo, cnt ) con las condiciones dadas. Después de los pasos anteriores para cada elemento, elimine el conteo de pares posibles iguales del conteo total e imprima ese valor. Siga los pasos a continuación para resolver el problema:

  1. Almacena la frecuencia de cada elemento en Map .
  2. Crea una variable para almacenar la contribución de cada elemento.
  3. La contribución de algún número x se puede calcular como freq[x]*(freq[x] – 1) dividido por 2 , donde freq[x] es la frecuencia de x .
  4. Recorra la array dada y elimine la contribución de cada elemento del recuento total y guárdelo en ans[] .
  5. Imprime todos los elementos almacenados en ans[] .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for
// the above approach
#include <bits/stdc++.h>
#define int long long int
using namespace std;
 
// Function to print the required
// count of pairs excluding the
// current element
void solve(int arr[], int n)
{
    // Store the frequency
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        mp[arr[i]]++;
    }
 
    // Find all the count
    int cnt = 0;
    for (auto x : mp) {
        cnt += ((x.second)
                * (x.second - 1) / 2);
    }
 
    int ans[n];
 
    // Delete the contribution of
    // each element for equal pairs
    for (int i = 0; i < n; i++) {
 
        ans[i] = cnt - (mp[arr[i]] - 1);
    }
 
    // Print the answer
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int32_t main()
{
    // Given array arr[]
    int arr[] = { 1, 1, 2, 1, 2 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    solve(arr, N);
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to print the required
// count of pairs excluding the
// current element
static void solve(int arr[],
                  int n)
{
  // Store the frequency
  HashMap<Integer,
          Integer> mp = new HashMap<Integer,
                                    Integer>();
  for (int i = 0; i < n; i++)
  {
    if(mp.containsKey(arr[i]))
    {
      mp.put(arr[i], mp.get(arr[i]) + 1);
    }
    else
    {
      mp.put(arr[i], 1);
    }
  }
 
  // Find all the count
  int cnt = 0;
  for (Map.Entry<Integer,
                 Integer> x : mp.entrySet())
  {
    cnt += ((x.getValue()) *
            (x.getValue() - 1) / 2);
  }
 
  int []ans = new int[n];
 
  // Delete the contribution of
  // each element for equal pairs
  for (int i = 0; i < n; i++)
  {
    ans[i] = cnt - (mp.get(arr[i]) - 1);
  }
 
  // Print the answer
  for (int i = 0; i < n; i++)
  {
    System.out.print(ans[i] + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  // Given array arr[]
  int arr[] = {1, 1, 2, 1, 2};
 
  int N = arr.length;
 
  // Function Call
  solve(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for
# the above approach
 
# Function to print required
# count of pairs excluding the
# current element
def solve(arr, n):
     
    # Store the frequency
    mp = {}
    for i in arr:
        mp[i] = mp.get(i, 0) + 1
 
    # Find all the count
    cnt = 0
    for x in mp:
        cnt += ((mp[x]) *
                (mp[x] - 1) // 2)
 
    ans = [0] * n
 
    # Delete the contribution of
    # each element for equal pairs
    for i in range(n):
        ans[i] = cnt - (mp[arr[i]] - 1)
 
    # Print the answer
    for i in ans:
        print(i, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [1, 1, 2, 1, 2]
 
    N = len(arr)
 
    # Function call
    solve(arr, N)
     
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to print the required
// count of pairs excluding the
// current element
static void solve(int []arr,
                  int n)
{
  // Store the frequency
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
  for (int i = 0; i < n; i++)
  {
    if(mp.ContainsKey(arr[i]))
    {
      mp[arr[i]] =  mp[arr[i]] + 1;
    }
    else
    {
      mp.Add(arr[i], 1);
    }
  }
 
  // Find all the count
  int cnt = 0;
  foreach (KeyValuePair<int,
                        int> x in mp)
  {
    cnt += ((x.Value) *
            (x.Value - 1) / 2);
  }
 
  int []ans = new int[n];
 
  // Delete the contribution of
  // each element for equal pairs
  for (int i = 0; i < n; i++)
  {
    ans[i] = cnt - (mp[arr[i]] - 1);
  }
 
  // Print the answer
  for (int i = 0; i < n; i++)
  {
    Console.Write(ans[i] + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {1, 1, 2, 1, 2};
 
  int N = arr.Length;
 
  // Function Call
  solve(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for
// the above approach
 
// Function to print the required
// count of pairs excluding the
// current element
function solve(arr, n)
{
    // Store the frequency
    var mp = new Map();
    for (var i = 0; i < n; i++) {
        if(mp.has(arr[i]))
            mp.set(arr[i], mp.get(arr[i])+1)
        else
            mp.set(arr[i], 1);
    }
 
    // Find all the count
    var cnt = 0;
    mp.forEach((value, key) => {
         
        cnt += ((value)
                * (value - 1) / 2);
    });
 
    var ans = Array(n);
 
    // Delete the contribution of
    // each element for equal pairs
    for (var i = 0; i < n; i++) {
 
        ans[i] = cnt - (mp.get(arr[i]) - 1);
    }
 
    // Print the answer
    for (var i = 0; i < n; i++) {
        document.write( ans[i] + " ");
    }
}
 
// Driver Code
// Given array arr[]
var arr = [1, 1, 2, 1, 2];
var N = arr.length;
// Function Call
solve(arr, N);
 
</script>
Producción: 

2 2 3 2 3

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por a_kash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *