Programa en C++ para comprobar si dos arrays son iguales o no

Dadas dos arrays arr1[] y arr2[] de longitud N y M respectivamente, la tarea es verificar si las dos arrays son iguales o no. 

Nota: Se dice que los arreglos son iguales si y solo si ambos arreglos contienen los mismos elementos y las frecuencias de cada elemento en ambos arreglos son las mismas.

Ejemplos:

Entrada: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {5, 4, 3, 2, 1}
Salida: Igual
Explicación: Como ambas arrays contienen los mismos elementos.

Entrada: arr1[] = {1, 5, 2, 7, 3, 8}, arr2[] = {8, 2, 3, 5, 7, 1}
Salida: Igual

Enfoque ingenuo: la forma básica de resolver el problema es la siguiente:

Aplique la ordenación en ambas arrays y luego haga coincidir cada elemento de una array con el elemento en el mismo índice de la otra array.

Siga los pasos mencionados a continuación para implementar la idea.

• Compruebe si la longitud de ambas arrays es igual o no
• Luego ordene ambas arrays, de modo que podamos comparar todos los elementos iguales.
• Itere linealmente sobre ambas arrays y verifique si los elementos son iguales o no,
• Si es igual, imprima Igual y, si no, imprima No igual.

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

// C++ program to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if both arrays are equal
bool checkArrays(int arr1[], int arr2[],
                 int n, int m)
{
    // If lengths of array are not equal
    // means array are not equal
    if (n != m)
        return false;
 
    // Sort both arrays
    sort(arr1, arr1 + n);
    sort(arr2, arr2 + m);
 
    // Linearly compare elements
    for (int i = 0; i < n; i++)
        if (arr1[i] != arr2[i])
            return false;
 
    // If elements are same
    return true;
}
 
// Driver Code
int main()
{
    int arr1[] = { 1, 2, 3, 4, 5 };
    int arr2[] = { 5, 4, 3, 2, 1 };
    int N = sizeof(arr1) / sizeof(int);
    int M = sizeof(arr2) / sizeof(int);
 
    // Function call
    if (checkArrays(arr1, arr2, N, M))
        cout << "Equal";
    else
        cout << "Not Equal";
    return 0;
}

Equal

Complejidad de tiempo: O(N * logN) 
Espacio auxiliar: O(1)

Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando Hashing (unordered_map),

Utilice hashing para contar la frecuencia de cada elemento de ambas arrays. Luego recorra las tablas hash de las arrays y haga coincidir las frecuencias de los elementos.

Siga los pasos mencionados a continuación para resolver el problema:

• Compruebe si la longitud de ambas arrays es igual o no
• Cree un mapa desordenado y almacene todos los elementos y la frecuencia de los elementos de arr1[] en el mapa.
• Recorra arr2[] y compruebe si el recuento de todos y cada uno de los elementos de arr2[] coincide con el recuento de arr1[] . Esto se puede hacer disminuyendo la frecuencia mientras se atraviesa en arr2[] .

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

// C++ program to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if both arrays are equal
bool checkArrays(int arr1[], int arr2[],
                 int n, int m)
{
    // If lengths of arrays are not equal
    if (n != m)
        return false;
 
    // Store arr1[] elements and
    // their frequencies in hash map
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
 
        mp[arr1[i]]++;
 
    // Traverse arr2[] elements and
    // check if all elements of arr2[] are
    // present same number of times or not.
    for (int i = 0; i < n; i++) {
 
        // If there is an element in arr2[],
        // but not in arr1[]
        if (mp.find(arr2[i]) == mp.end())
            return false;
 
        // If an element of arr2[] appears
        // more times than it appears in arr1[]
        if (mp[arr2[i]] == 0)
            return false;
 
        // Decrease the count of arr2 elements
        // in the unordered map
        mp[arr2[i]]--;
    }
    return true;
}
 
// Driver Code
int main()
{
    int arr1[] = { 1, 2, 3, 4, 5 };
    int arr2[] = { 4, 3, 1, 5, 2 };
    int N = sizeof(arr1) / sizeof(int);
    int M = sizeof(arr2) / sizeof(int);
 
    // Function call
    if (checkArrays(arr1, arr2, N, M))
        cout << "Equal";
    else
        cout << "Not Equal";
    return 0;
}

Equal

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