İki massivin bərabər olub olmadığını yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Goldman Sachs MAQ o9 həlləri Taksi4Sure Twilio
Geyim Sükut çeşidləyiciBaxılıb 36

“İki massivin bərabər olub olmadığını yoxlayın” problemi sizə iki verildiyini bildirir seriallar. Problem ifadəsində deyilir ki, verilən massivlərin bərabər olub-olmadığını müəyyənləşdirməlisiniz.

İki massivin bərabər olub olmadığını yoxlayınPin

misal

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

İki massivin bərabər olub olmadığını yoxlamaq üçün alqoritm

  1. Hər iki massivin də uzunluğunu seçin l1l2 müvafiq.
  2. Uzunluqların hər ikisinin bərabər olmadığını yoxlayın, doğrudursa, yalnış qaytarın.
  3. Hər elementin frekanslarını xəritədə saxlayın və sayın.
  4. İkinci sıra keçərək,
    1. Bir olub olmadığını yoxlayın xəritə arr2 elementlərindən ibarət deyil, false qaytarın.
    2. Bu elementin tezliyinin doğrudursa 0-a bərabər olub olmadığını yoxlayın, sonra yalan qayıdın.
    3. Cari elementin tezliyini 1-ə endirin, onu cari elementin tezlik yerində saxlayın.
  5. Bütün dəyərlər keçənə qədər 4-cü addımı təkrarlayın.
  6. Doğru qayıdın.

Izahat

Verilən iki massivin bərabər olub olmadığını öyrənməyimizi istəyən bir problem verilir. Bunu həll etmək üçün istifadə edəcəyik Hashing, vaxtımıza qənaət etməyə kömək edir və zamanın mürəkkəbliyini azaldır.

Yapacağımız ilk şey, hər iki massivin də uzunluğunu öyrənməkdir, çünki şərt üçün, əgər massivlər bərabərdirsə, bir şərt yerinə yetirilməlidir və o da hər iki massivin uzunluğu bərabər olmalıdır, buna görə hər iki massivin də uzunluğunu tapdığımızda bərabər olub olmadığını yoxlamalıyıq, bərabər olmadığı təqdirdə yalnış qayıdırıq və daha davam etməyə ehtiyac yoxdur. Bərabər olduğu aşkar edilərsə, yalnız biz irəliləyirik.

Dizinin hər elementinin [] tezliklərini sayaraq xəritədə saxlayacağıq. Fərz edək ki, iki və ya üç dəfə tək bir element tapdıq, yalnız tezliyini 1 artırırıq və artırırıq və həmin elementlə birlikdə eyni tezliyə saxlayırıq.

misal

Bir nümunəni nəzərdən keçirək:

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

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

Massivi [1] keçdikdən və tezlik elementləri ilə bütün elementləri xəritəyə qoyduqdan sonra xəritə aşağıdakı kimidir.

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

Xəritəmizdəki dəyərlərə sahib olduğumuz üçün ikinci massivi keçib bir xəritədə array2 elementləri olub olmadığını yoxlamalıyıq, əgər array2 [] elementlərini içermirsə, yalnış qayıdırıq. Cari elementin tezliyi 0-a bərabərdirsə, doğrudursa, yalnış qayıdırıq. Sonra cari element tezliyinin dəyərini alırıq və 1-ə endiririk və yenidən xəritəyə dəyər qoyuruq. Beləliklə, eyni say birdən çox dəfə mövcudsa, bu növbəti dəfə kömək edəcəkdir. Bu şərt o halda daxil edilir. Döngüdən çıxdıqdan sonra, massivdəki bütün rəqəmlərə sahib olduğumuzu və massivləri bərabərləşdirdiyimizi göstərir. O zaman doğru qayıdacağıq.

İki sıra bərabər olub olmadığını yoxlamaq üçün C ++ kodu

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

İki sıra bərabər olub olmadığını yoxlamaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. HashMap-in istifadəsi xətti zaman mürəkkəbliyinə nail olmağa imkan verdi, əks halda daha çox vaxt alardı.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır. Bütün elementlər fərqli olacaqsa, xəritəmiz girişdəki nömrələrin hər biri üçün açar dəyərə sahib olacaqdır. Beləliklə kosmik mürəkkəblik də doğrudur.

Translate »