두 배열이 같은지 확인하십시오.


난이도 중급
자주 묻는 질문 Accenture 골드만 삭스 MAQ o9 솔루션 Taxi4Sure Twilio
배열 해시 정렬

“두 배열이 같은지 확인하십시오”라는 문제는 배열. 문제 설명은 주어진 배열이 같은지 아닌지를 결정해야한다고 말합니다.

두 배열이 같은지 확인하십시오.

arr1[] = { 1, 4, 2, 5, 2 };
arr2[] = { 2, 1, 5, 4, 2 };
Yes, Arrays are equal !!
arr1[] = { 1, 3, 2, 7, 2 };
arr2[] = { 2, 1, 5, 3, 2 };
No, Arrays are not equal !!

두 배열이 같은지 확인하는 알고리즘

  1. 두 배열의 길이를 l1l2 각각.
  2. 두 길이가 같지 않은지 확인하고 참이면 거짓을 반환합니다.
  3. 지도에 각 요소의 빈도를 저장하고 계산합니다.
  4. 두 번째 배열을 순회하면서
    1. 확인하십시오 지도 arr2 요소가 포함되어 있지 않으면 false를 반환합니다.
    2. 특정 요소의 빈도가 참이면 0인지 확인한 다음 거짓을 반환합니다.
    3. 현재 요소의 주파수를 1로 줄이고 현재 요소의 주파수 위치에 저장합니다.
  5. 모든 값이 순회 될 때까지 4 단계를 반복합니다.
  6. true를 반환합니다.

설명

주어진 두 배열이 같은지 아닌지를 알아내는 문제가 있습니다. 이것을 해결하기 위해 우리는 해싱, 시간을 절약하고 시간의 복잡성을 줄이는 데 도움이됩니다.

가장 먼저 할 일은 두 배열의 길이를 알아내는 것입니다. 조건에 대해 배열이 같으면 하나의 조건이 충족되어야하고 두 배열의 길이가 같아야하기 때문입니다. 두 배열의 길이를 찾으면 같은지 아닌지 확인하고, 같지 않은 경우 false를 반환하고 더 이상 진행할 필요가 없습니다. 동일하다고 판명되면 우리는 더 멀리 나아갑니다.

array1 []의 각 요소의 빈도를 계산하고 맵에 저장합니다. 단일 요소를 두 번 또는 세 번 찾은 경우 빈도를 1 씩 업데이트하고 늘리고 해당 요소와 함께 동일한 빈도에 저장합니다.

예를 들어 보겠습니다.

arr1 [] = {1, 4, 2, 5, 2};

arr2 [] = {2, 1, 5, 4, 2};

array1 []을 횡단하고 주파수가있는 모든 요소를 ​​맵에 넣은 후 다음과 같은 맵을 갖게됩니다.

myMap={1:1, 2:2, 4:1, 5:1}

맵에 값이 있으므로 두 번째 배열을 탐색하고 맵에 array2 요소가 있는지 확인해야합니다. array2 [] 요소가 포함되어 있지 않으면 false를 반환합니다. 현재 요소의 빈도가 0인지 확인하고 참이면 거짓을 반환합니다. 그런 다음 현재 요소 빈도의 값을 가져 와서 1로 줄이고 값을 다시 맵에 넣습니다. 따라서 동일한 숫자가 두 번 이상 존재하면 다음에 도움이 될 것입니다. 이 조건은이 경우에 포함됩니다. 루프에서 나오면 배열에있는 모든 숫자가 비슷하고 배열을 동일하게 만듭니다. 그러면 우리는 진실을 반환 할 것입니다.

두 배열이 같은지 확인하는 C ++ 코드

#include <unordered_map>
#include<iostream>

using namespace std;

bool areTwoArrayEqual(int arr1[], int arr2[], int l1, int l2)
{
    if (l1 !=l2)
        return false;

    unordered_map<int, int> myMap;
    for (int i = 0; i < l1; i++)
    {
        myMap[arr1[i]]++;
    }
    for (int i = 0; i < l1; i++)
    {
        if (myMap.find(arr2[i]) == myMap.end())
            return false;

        if (myMap[arr2[i]] == 0)
            return false;

        myMap[arr2[i]]--;
    }

    return true;
}
int main()
{
    int arr1[] = { 1, 4, 2, 5, 2 };
    int arr2[] = { 2, 1, 5, 4, 2 };

    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);

    if (areTwoArrayEqual(arr1, arr2, l1, l2))
        cout << "Yes, Arrays are equal !!";
    else
        cout << "No, Arrays are not equal !!";
    return 0;
}
Yes, Arrays are equal !!

두 배열이 같은지 확인하는 Java 코드

import java.util.*;

class twoArrayEqual
{
    public static boolean areTwoArrayEqual(int arr1[], int arr2[])
    {
        int l1 = arr1.length;
        int l2 = arr2.length;

        if (l1 != l2)
            return false;

        Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();
        int count = 0;
        for (int i = 0; i < l1; i++)
        {
            if (myMap.get(arr1[i]) == null)
                myMap.put(arr1[i], 1);
            else
            {
                count = myMap.get(arr1[i]);
                count++;
                myMap.put(arr1[i], count);
            }
        }
        for (int i = 0; i < l1; i++)
        {
            if (!myMap.containsKey(arr2[i]))
                return false;

            if (myMap.get(arr2[i]) == 0)
                return false;

            count = myMap.get(arr2[i]);
            --count;
            myMap.put(arr2[i], count);
        }

        return true;
    }
    public static void main(String[] args)
    {
        int arr1[] = { 1, 4, 2, 5, 2 };
        int arr2[] = { 2, 1, 5, 4, 2 };

        if (areTwoArrayEqual(arr1, arr2))
            System.out.println("Yes, Arrays are equal !!");
        else
            System.out.println("No, Arrays are not equal !!");
    }
}
Yes, Arrays are equal !!

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. HashMap을 사용하면 선형 시간 복잡성을 달성 할 수있었습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 모든 요소가 구별되는 경우 맵은 입력의 각 숫자에 대한 키-값을 갖습니다. 따라서 공간 복잡성도 선형입니다.