Проверите да ли су два низа једнака или не


Ниво тешкоће Средњи
Често питани у Аццентуре Голдман Сакс МАК о9 решења Таки4Суре Твилио
Ред Хасх сортирање

Проблем „Провери да ли су два низа једнака или не“ наводи да су ти дата два низови. Изјава о проблему каже да морате утврдити да ли су дати низови једнаки или не.

Проверите да ли су два низа једнака или не

Пример

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. Подесите дужину оба низа на l1 l2 респективно.
  2. Проверите да ли су обе дужине једнаке, ако је тачно, вратите фалсе.
  3. Похраните и пребројите фреквенције сваког елемента на мапи.
  4. Прелазећи други низ,
    1. Проверите да ли је а Мапа не садржи арр2 елементе, врати фалсе.
    2. Проверите да ли је фреквенција одређеног елемента једнака 0 ако је труе, а затим вратите фалсе.
    3. Смањите фреквенцију тренутног елемента за 1, похраните га на то место фреквенције тренутног елемента.
  5. Понављајте 4. корак док се не пређу све вредности.
  6. Повратак истинит.

Објашњење

Имамо задатак који тражи да сазнамо да ли су дата два низа једнака или не. Да бисмо то решили, користићемо се Хасхинг, помаже у уштеди нашег времена и смањује временску сложеност.

Прво што ћемо урадити је да откријемо дужину оба низа јер за услов, ако су низови једнаки, треба испунити један услов, а то је дужина оба низа, тако да када пронађемо дужину оба низа, само треба да проверимо да ли је једнако или не, ако се не утврди да је једнако, враћамо фалсе и не морамо даље. Ако се утврди да је једнако, онда само идемо даље.

Бројићемо и меморисати фреквенције сваког елемента низа1 [] на мапу. Претпоставимо да два пута или три пута пронађемо један елемент, само ажурирамо и повећавамо његову фреквенцију за 1 и складиштимо на ту исту фреквенцију заједно са тим елементом.

Пример

Размотримо пример:

арр1 [] = {1, 4, 2, 5, 2};

арр2 [] = {2, 1, 5, 4, 2};

Након преласка низа1 [] и стављања свих елемената са њиховим фреквенцијама на мапу имамо мапу на следећи начин.

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

Како на нашој мапи имамо вредности, морамо прећи други низ и проверити да ли мапа садржи елементе арраи2, ако не садржи елементе арраи2 [], онда враћамо фалсе. Проверићемо да ли је фреквенција тренутног елемента једнака 0, ако се утврди да је тачна, онда враћамо фалсе. Затим узмемо вредност тренутне фреквенције елемента и смањимо на 1 и поново ставимо вредност на мапу. Дакле, ово ће вам помоћи следећи пут ако исти број постоји више пута. Овај услов је укључен у тај случај. Једном када изађемо из петље, то значи да имамо све бројеве сличне у низу и да низове учинимо једнакима. Тада ћемо се вратити истинито.

Ц ++ код за проверу да ли су два низа једнака или не

#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 !!

Јава код за проверу да ли су два низа једнака или не

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 !!

Анализа сложености

Сложеност времена

Он) где „Н“ је број елемената у низу. Коришћење ХасхМап-а нам је омогућило да постигнемо линеарну временску сложеност, иначе би било потребно много више времена.

Сложеност простора

Он) где „Н“ је број елемената у низу. Ако ће се сви елементи разликовати, наша мапа ће имати кључ / вредност за сваки од бројева на улазу. Стога је сложеност простора такође линеарна.