Saltar al contenido

Programa en C++ para verificar si dos arreglos son iguales o no

2022 05 24 11 03 38 Cppstln Article Ad.webp.webp Programa en C++ para verificar si dos arreglos son iguales o no

Dadas dos matrices arr1[] y arr2[] de longitud norte y metro respectivamente, la tarea es verificar si las dos matrices son iguales o no.

Observación: 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:

Aporte: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {5, 4, 3, 2, 1}
Salida : Equivalente
Explicación: Porque ambas matrices contienen los mismos elementos.

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

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

Aplique ordenación a ambas matrices, luego haga coincidir cada elemento de una matriz con el elemento con el mismo índice de la otra matriz.

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

  • Compruebe si la longitud de ambas matrices es igual o no
  • Después tipo ambas matrices, por lo que podemos comparar todos los elementos iguales.
  • Iterar linealmente sobre ambas matrices y verificar 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++

 

#include <bits/stdc++.h>

using namespace std;

 

bool checkArrays(int arr1[], int arr2[],

                 int n, int m)

{

    

    

    if (n != m)

        return false;

 

    

    sort(arr1, arr1 + n);

    sort(arr2, arr2 + m);

 

    

    for (int i = 0; i < n; i++)

        if (arr1[i] != arr2[i])

            return false;

 

    

    return true;

}

 

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);

 

    

    if (checkArrays(arr1, arr2, N, M))

        cout << "Equal";

    else

        cout << "Not Equal";

    return 0;

}

Complejidad del tiempo: O(N * registroN)
cuarto auxiliar: O(1)

Enfoque eficiente: El problema se puede resolver de manera eficiente con Hashing (unordered_map),

Utilice hashing para contar la frecuencia de cada elemento de ambas matrices. Luego revise las tablas hash de las matrices y ajuste las frecuencias de los elementos.

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

  • Compruebe si la longitud de ambas matrices es igual o no
  • Cree un mapa desordenado y guarde todos los elementos y la frecuencia de los elementos de arr1[] en el mapa.
  • para cruzar arr2[] y verifique si el número de cada elemento en arr2[] corresponde a la cuenta en arr1[]† Esto se puede hacer bajando la frecuencia durante el rodaje. arr2[]

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

C++

 

#include <bits/stdc++.h>

using namespace std;

 

bool checkArrays(int arr1[], int arr2[],

                 int n, int m)

{

    

    if (n != m)

        return false;

 

    

    

    unordered_map<int, int> mp;

    for (int i = 0; i < n; i++)

 

        mp[arr1[i]]++;

 

    

    

    

    for (int i = 0; i < n; i++) {

 

        

        

        if (mp.find(arr2[i]) == mp.end())

            return false;

 

        

        

        if (mp[arr2[i]] == 0)

            return false;

 

        

        

        mp[arr2[i]]--;

    }

    return true;

}

 

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);

 

    

    if (checkArrays(arr1, arr2, N, M))

        cout << "Equal";

    else

        cout << "Not Equal";

    return 0;

}

Complejidad del tiempo: A)
cuarto auxiliar: A)

2022 05 24 11 03 38 Cppstln Article Ad.webp Programa en C++ para verificar si dos arreglos son iguales o no