Cuente el número de elementos comunes entre dos arrays

Dadas dos arrays a[] y b[] , la tarea es encontrar el recuento de elementos comunes en ambas arrays dadas. Tenga en cuenta que ambas arrays contienen enteros positivos distintos (individualmente).
Ejemplos: 
 

Entrada: a[] = {1, 2, 3}, b[] = {2, 4, 3} 
Salida: 2 
2 y 3 son comunes a ambas arrays.
Entrada: a[] = {1, 4, 7, 2, 3}, b[] = {2, 11, 7, 4, 15, 20, 24} 
Salida: 3 
 

Enfoque 1: Usaremos 3 bits del mismo tamaño. Primero recorreremos la primera array y estableceremos el bit 1 en la posición a[i] en el primer conjunto de bits. 
Después de eso, atravesaremos la segunda array y estableceremos el bit 1 en la posición b[i] en el segundo conjunto de bits. 
Por último, encontraremos el AND bit a bit de ambos conjuntos de bits y si la i ^-ésima posición del conjunto de bits resultante es 1 , implica que la i ^-ésima posición del primer y segundo conjunto de bits también son 1 e i es el elemento común en ambas arrays.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
bitset<MAX> bit1, bit2, bit3;
 
// Function to return the count of common elements
int count_common(int a[], int n, int b[], int m)
{
 
    // Traverse the first array
    for (int i = 0; i < n; i++) {
 
        // Set 1 at position a[i]
        bit1.set(a[i]);
    }
 
    // Traverse the second array
    for (int i = 0; i < m; i++) {
 
        // Set 1 at position b[i]
        bit2.set(b[i]);
    }
 
    // Bitwise AND of both the bitsets
    bit3 = bit1 & bit2;
 
    // Find the count of 1's
    int count = bit3.count();
 
    return count;
}
 
// Driver code
int main()
{
 
    int a[] = { 1, 4, 7, 2, 3 };
    int b[] = { 2, 11, 7, 4, 15, 20, 24 };
    int n = sizeof(a) / sizeof(a[0]);
    int m = sizeof(b) / sizeof(b[0]);
 
    cout << count_common(a, n, b, m);
 
    return 0;
}

# Python3 implementation of the approach
 
MAX = 100000
bit1 , bit2, bit3 = 0, 0, 0
 
# Function to return the count of common elements
def count_common(a, n, b, m) :
 
    # Traverse the first array
    for i in range(n) :
         
        global bit1, bit2, bit3
         
        # Set 1 at (index)position a[i]
        bit1 = bit1 | (1<<a[i])
 
    # Traverse the second array
    for i in range(m) :
 
        # Set 1 at (index)position b[i]
        bit2 = bit2 | (1<<b[i])
 
    # Bitwise AND of both the bitsets
    bit3 = bit1 & bit2;
 
    # Find the count of 1's
    count = bin(bit3).count('1');
 
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 1, 4, 7, 2, 3 ];
    b = [ 2, 11, 7, 4, 15, 20, 24 ];
    n = len(a);
    m = len(b);
 
    print(count_common(a, n, b, m));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG {
  static int bit1 = 0;
  static int bit2 = 0;
  static int bit3 = 0;
 
  // Function to return the count of common elements
  static int count_common(int[] a, int n, int[] b, int m)
  {
 
    // Traverse the first array
    for (int i = 0; i < n; i++) {
      // Set 1 at (index)position a[i]
      bit1 = bit1 | (1 << a[i]);
    }
    // Traverse the second array
    for (int i = 0; i < m; i++) {
 
      // Set 1 at (index)position b[i]
      bit2 = bit2 | (1 << b[i]);
    }
 
    // Bitwise AND of both the bitsets
    bit3 = bit1 & bit2;
 
    // Find the count of 1's
    var count
      = Convert.ToString(bit3, 2).Split("1").Length
      - 1;
    return count;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int[] a = { 1, 4, 7, 2, 3 };
    int[] b = { 2, 11, 7, 4, 15, 20, 24 };
    int n = a.Length;
    int m = b.Length;
 
    Console.WriteLine(count_common(a, n, b, m));
  }
}
 
// This code is contributed by phasing17

//JavaScript implementation of the approach
 
const MAX = 100000;
let bit1 = 0;
let bit2 = 0;
let bit3 = 0;
 
// Function to return the count of common elements
function count_common(a, n, b, m)
{
 
    // Traverse the first array
    for (var i = 0; i < n; i++)
    {
        // Set 1 at (index)position a[i]
        bit1 = bit1 | (1<<a[i]);
    }
    // Traverse the second array
    for (var i = 0; i < m; i++)
    {
 
        // Set 1 at (index)position b[i]
        bit2 = bit2 | (1<<b[i]);
    }
 
    // Bitwise AND of both the bitsets
    bit3 = bit1 & bit2;
 
    // Find the count of 1's
    var count = bit3.toString(2).split("1").length - 1;
    return count;
}
 
 
// Driver code
var a = [ 1, 4, 7, 2, 3 ];
var b = [ 2, 11, 7, 4, 15, 20, 24 ];
var n = a.length;
var m = b.length;
 
console.log(count_common(a, n, b, m));
 
//This code is contributed by phasing17

3

Complejidad temporal: O(n + m)

Espacio Auxiliar: O(MAX)

Enfoque 2: también podemos usar hashmap para almacenar frecuencias de cada elemento de ambas arrays a[] y b[] y sumar el valor mínimo para la frecuencia de cada elemento.

Siga los pasos dados para resolver el problema:

1. Atraviese la array a[] y almacene todas las frecuencias en map freq1 .

2. Atraviese la array b[] y almacene todas las frecuencias en map freq2 .

3. Recorra el mapa freq1 y sume el valor mínimo entre x.second y freq2 [x.first] en result .

4. Devuelva el resultado como respuesta final.

#include <bits/stdc++.h>
using namespace std;
 
int count_common(int *a, int& n, int *b, int& m)
{
    unordered_map<int,int>freq1,freq2;
    int result=0;
     
    for(int i=0;i<n;i++)
        freq1[a[i]]++;
     
    for(int i=0;i<m;i++)
        freq2[b[i]]++;
     
    for(auto& x:freq1)
        result+=min(x.second,freq2[x.first]);
     
    return result;
}
 
// driver's code
int main()
{
    int a[]={1,2,3};
    int n=sizeof(a)/sizeof(a[0]);
    int b[]={2,4,3};
    int m=sizeof(b)/sizeof(b[0]);
     
    cout<<count_common(a,n,b,m);
 
    return 0;
}
// this code is contributed by prophet1999

Complejidad temporal: O(n+m)

Espacio Auxiliar: O(n+m)