Comprobar si dos arrays son iguales o no

Dadas dos arrays, arr1 y arr2 de igual longitud N , la tarea es encontrar si las arrays dadas son iguales o no. 

Se dice que dos arrays son iguales si:

• ambos contienen el mismo conjunto de elementos, 
• los arreglos (o permutaciones) de los elementos pueden o no ser iguales.
• Si hay repeticiones, la cantidad de elementos repetidos también debe ser la misma para que dos arrays sean iguales.

Ejemplos: 

Entrada: arr1[] = {1, 2, 5, 4, 0}, arr2[] = {2, 4, 5, 0, 1}
Salida: Sí

Entrada: arr1[] = {1, 2, 5, 4, 0, 2, 1}, arr2[] = {2, 4, 5, 0, 1, 1, 2} 
Salida: Sí

 Entrada: arr1[] = {1, 7, 1}, arr2[] = {7, 7, 1}
Salida: No

Enfoque 1 (Clasificación): Siga los pasos a continuación para resolver el problema usando este enfoque:

• Ordenar ambas arrays
• Luego compare linealmente los elementos de ambas arrays
• Si todos son iguales, devuelve verdadero, de lo contrario, devuelve falso

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

// C++ program to find given two array
// are equal or not
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if arr1[0..n-1] and arr2[0..m-1]
// contain same elements.
bool areEqual(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 all elements were same.
    return true;
}
 
// Driver's Code
int main()
{
    int arr1[] = { 3, 5, 2, 5, 2 };
    int arr2[] = { 2, 3, 5, 5, 2 };
    int N = sizeof(arr1) / sizeof(int);
    int M = sizeof(arr2) / sizeof(int);
 
    // Function call
    if (areEqual(arr1, arr2, N, M))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

// Java program to find given two array
// are equal or not
import java.io.*;
import java.util.*;
 
class GFG {
    // Returns true if arr1[0..n-1] and
    // arr2[0..m-1] contain same elements.
    public static boolean areEqual(int arr1[], int arr2[])
    {
        int N = arr1.length;
        int M = arr2.length;
 
        // If lengths of array are not equal means
        // array are not equal
        if (N != M)
            return false;
 
        // Sort both arrays
        Arrays.sort(arr1);
        Arrays.sort(arr2);
 
        // Linearly compare elements
        for (int i = 0; i < N; i++)
            if (arr1[i] != arr2[i])
                return false;
 
        // If all elements were same.
        return true;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = { 3, 5, 2, 5, 2 };
        int arr2[] = { 2, 3, 5, 5, 2 };
 
        // Function call
        if (areEqual(arr1, arr2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

# Python3 program to find given
# two array are equal or not
 
# Returns true if arr1[0..n-1] and
# arr2[0..m-1] contain same elements.
 
 
def areEqual(arr1, arr2, N, M):
 
    # If lengths of array are not
    # equal means array are not equal
    if (N != M):
        return False
 
    # Sort both arrays
    arr1.sort()
    arr2.sort()
 
    # Linearly compare elements
    for i in range(0, N):
        if (arr1[i] != arr2[i]):
            return False
 
    # If all elements were same.
    return True
 
 
# Driver Code
if __name__ == "__main__":
    arr1 = [3, 5, 2, 5, 2]
    arr2 = [2, 3, 5, 5, 2]
    n = len(arr1)
    m = len(arr2)
 
    if (areEqual(arr1, arr2, n, m)):
        print("Yes")
    else:
        print("No")

// C# program for the above approach
using System;
 
class GFG {
 
    // Returns true if arr1[0..n-1] and
    // arr2[0..m-1] contain same elements.
    public static bool areEqual(int[] arr1, int[] arr2)
    {
        int N = arr1.Length;
        int M = arr2.Length;
 
        // If lengths of array are not
        // equal means array are not equal
        if (N != M)
            return false;
 
        // Sort both arrays
        Array.Sort(arr1);
        Array.Sort(arr2);
 
        // Linearly compare elements
        for (int i = 0; i < N; i++)
            if (arr1[i] != arr2[i])
                return false;
 
        // If all elements were same.
        return true;
    }
 
    // Driver's code
    public static void Main()
    {
        int[] arr1 = { 3, 5, 2, 5, 2 };
        int[] arr2 = { 2, 3, 5, 5, 2 };
 
        // Function call
        if (areEqual(arr1, arr2))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to find given
// two array are equal or not
 
// Returns true if arr1[0..n-1]
// and arr2[0..m-1] contain same elements.
function areEqual( $arr1, $arr2, $N, $M)
{
    // If lengths of array
    // are not equal means
    // array are not equal
    if ($N != $M)
        return false;
 
    // Sort both arrays
    sort($arr1);
    sort($arr2);
 
    // Linearly compare elements
    for ( $i = 0; $i < $N; $i++)
        if ($arr1[$i] != $arr2[$i])
            return false;
 
    // If all elements were same.
    return true;
}
 
// Driver Code
$arr1 = array(3, 5, 2, 5, 2);
$arr2 = array(2, 3, 5, 5, 2);
$N = count($arr1);
$M = count($arr2);
 
// Function call
if (areEqual($arr1, $arr2, $N, $M))
    echo "Yes";
else
    echo "No";
 
?>

<script>
 
// JavaScript program for the above approach
 
    // Returns true if arr1[0..n-1] and arr2[0..m-1]
    // contain same elements.
    function areEqual(arr1, arr2)
    {
        let N = arr1.length;
        let M = arr2.length;
 
        // If lengths of array are not equal means
        // array are not equal
        if (N != M)
            return false;
 
        // Sort both arrays
        arr1.sort();
        arr2.sort();
 
        // Linearly compare elements
        for (let i = 0; i < N; i++)
            if (arr1[i] != arr2[i])
                return false;
 
        // If all elements were same.
        return true;
    }
 
// Driver Code
    let arr1 = [3, 5, 2, 5, 2];
    let arr2 = [2, 3, 5, 5, 2];
 
    if (areEqual(arr1, arr2))
        document.write("Yes");
    else
        document.write("No");
 
</script>

Yes

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

Enfoque 2 (hashing): una solución eficiente para este enfoque es usar Hashing . 

Almacene el recuento de todos los elementos de arr1[] en una tabla hash. Luego recorra arr2[] y verifique si el conteo de cada elemento en arr2[] coincide con el conteo de elementos de arr1[].

Siga los pasos que se mencionan a continuación para implementar el enfoque:

• Primero verifique si la longitud de arr1 no es igual a la longitud de arr2 y luego devuelva falso
• Luego recorra la primera array y almacene el recuento de cada elemento en el mapa hash
• Luego recorra la segunda array y disminuya el recuento de sus elementos en el mapa hash. Si ese elemento no está presente o el recuento de ese elemento es 
  cero en el mapa hash, devuelva falso, de lo contrario, disminuya el recuento de ese elemento
• Devuelve verdadero al final, ya que ambas arrays son iguales ahora

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if arr1[0..N-1] and arr2[0..M-1]
// contain same elements.
bool areEqual(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 counts 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's Code
int main()
{
    int arr1[] = { 3, 5, 2, 5, 2 };
    int arr2[] = { 2, 3, 5, 5, 2 };
    int N = sizeof(arr1) / sizeof(int);
    int M = sizeof(arr2) / sizeof(int);
 
    // Function call
    if (areEqual(arr1, arr2, N, M))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Returns true if arr1[0..N-1] and arr2[0..M-1]
    // contain same elements.
    public static boolean areEqual(int arr1[], int arr2[])
    {
        int N = arr1.length;
        int M = arr2.length;
 
        // If lengths of arrays are not equal
        if (N != M)
            return false;
 
        // Store arr1[] elements and their counts in
        // hash map
        Map<Integer, Integer> map
            = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (map.get(arr1[i]) == null)
                map.put(arr1[i], 1);
            else {
                count = map.get(arr1[i]);
                count++;
                map.put(arr1[i], count);
            }
        }
 
        // 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 (!map.containsKey(arr2[i]))
                return false;
 
            // If an element of arr2[] appears more
            // times than it appears in arr1[]
            if (map.get(arr2[i]) == 0)
                return false;
 
            count = map.get(arr2[i]);
            --count;
            map.put(arr2[i], count);
        }
 
        return true;
    }
 
    // Driver's code
    public static void main(String[] args)
    {
        int arr1[] = { 3, 5, 2, 5, 2 };
        int arr2[] = { 2, 3, 5, 5, 2 };
 
        // Function call
        if (areEqual(arr1, arr2))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

# Python3 program for the above approach
 
# Returns true if arr1[0..N-1] and
# arr2[0..M-1] contain same elements.
 
 
def is_arr_equal(arr1, arr2):
        # Check if the length of arrays are
    # equal or not: A Easy Logic Check
    if len(arr1) != len(arr2):
        return False
 
    # Create a dict named count to
    # store counts of each element
    count = {}
    # Store the elements of arr1
    # and their counts in the dictionary
    for i in arr1:
        if i in count:
                # Element already in dict, simply increment its count
            count[i] += 1
        else:
                # Element found for first time, initialize it with value 1.
            count[i] = 1
 
    # Traverse through arr2 and compare
    # the elements and its count with
    # the elements of arr1
    for i in arr2:
        # Return false if the element
        # is not in count or if any element
        # appears more no. of times than in arr1
        if i not in count or count[i] == 0:
            return False
        else:
                # If element is found, decrement
                # its value in the dictionary
            count[i] -= 1
    # Return true if both arr1 and
    # arr2 are equal
    return True
 
 
# Driver Code
if __name__ == "__main__":
    arr1 = [3, 5, 2, 5, 2]
    arr2 = [2, 3, 5, 5, 2]
 
    if is_arr_equal(arr1, arr2):
        print("Yes")
    else:
        print("No")

// C# program to find given two array
// are equal or not using hashing technique
using System;
using System.Collections.Generic;
 
class GFG {
    // Returns true if arr1[0..N-1] and arr2[0..M-1]
    // contain same elements.
    public static bool areEqual(int[] arr1, int[] arr2)
    {
        int N = arr1.Length;
        int M = arr2.Length;
 
        // If lengths of arrays are not equal
        if (N != M)
            return false;
 
        // Store arr1[] elements and their counts in
        // hash map
        Dictionary<int, int> map
            = new Dictionary<int, int>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (!map.ContainsKey(arr1[i]))
                map.Add(arr1[i], 1);
            else {
                count = map[arr1[i]];
                count++;
                map.Remove(arr1[i]);
                map.Add(arr1[i], count);
            }
        }
 
        // 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 (!map.ContainsKey(arr2[i]))
                return false;
 
            // If an element of arr2[] appears more
            // times than it appears in arr1[]
            if (map[arr2[i]] == 0)
                return false;
 
            count = map[arr2[i]];
            --count;
 
            if (!map.ContainsKey(arr2[i]))
                map.Add(arr2[i], count);
        }
        return true;
    }
 
    // Driver's code
    public static void Main(String[] args)
    {
        int[] arr1 = { 3, 5, 2, 5, 2 };
        int[] arr2 = { 2, 3, 5, 5, 2 };
 
        // Function call
        if (areEqual(arr1, arr2))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
 
//  Javascript program to find given two array
// are equal or not using hashing technique
 
    // Returns true if arr1[0..N-1] and arr2[0..M-1]
    // contain same elements.
    function areEqual(arr1, arr2)
    {
        let N = arr1.length;
        let M = arr2.length;
  
        // If lengths of arrays are not equal
        if (N != M)
            return false;
  
        // Store arr1[] elements and their counts in
        // hash map
        let map
            = new Map();
        let count = 0;
        for (let i = 0; i < N; i++) {
            if (map.get(arr1[i]) == null)
                map.set(arr1[i], 1);
            else {
                count = map.get(arr1[i]);
                count++;
                map.set(arr1[i], count);
            }
        }
  
        // Traverse arr2[] elements and check if all
        // elements of arr2[] are present same number
        // of times or not.
        for (let i = 0; i < N; i++) {
            // If there is an element in arr2[], but
            // not in arr1[]
            if (!map.has(arr2[i]))
                return false;
  
            // If an element of arr2[] appears more
            // times than it appears in arr1[]
            if (map.get(arr2[i]) == 0)
                return false;
  
            count = map.get(arr2[i]);
            --count;
            map.set(arr2[i], count);
        }
  
        return true;
    }
     
    // Driver code
     
    let arr1 = [3, 5, 2, 5, 2];
    let arr2 = [2, 3, 5, 5, 2];
      
    // Function call
        if (areEqual(arr1, arr2))
            document.write("Yes");
        else
            document.write("No");
     
</script>

Yes

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