بررسی کنید که آیا دو آرایه برابر هستند یا نه  


سطح دشواری متوسط
اغلب در 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. طول هر دو آرایه را بر روی تنظیم کنید l1 و l2 بود.
  2. بررسی کنید که هر دو طول برابر نیستند ، اگر درست است ، نادرست برگردانید.
  3. فرکانس های هر عنصر را در نقشه ذخیره و حساب کنید.
  4. عبور از آرایه دوم ،
    1. بررسی کنید که آیا نقشه شامل عناصر arr2 نیست ، false را برگردانید.
    2. بررسی کنید که آیا فرکانس آن عنصر خاص در صورت درست برابر با 0 است یا خیر ، false را برگردانید.
    3. فرکانس عنصر جریان را 1 کاهش دهید ، آن را در آن مکان از فرکانس عنصر فعلی ذخیره کنید.
  5. مرحله 4 را تکرار کنید تا تمام مقادیر عبور داده شود.
  6. درست برگرد

توضیح

به ما یک مسئله داده می شود که می خواهد بفهمد که آیا دو آرایه داده شده برابر هستند یا خیر. برای حل این ما می خواهیم استفاده کنیم هشی کردن، به صرفه جویی در وقت ما کمک می کند و پیچیدگی زمان را کاهش می دهد.

همچنین مشاهده کنید
ادغام مرتب سازی

اولین کاری که ما می خواهیم انجام دهیم این است که طول هر دو آرایه را دریابیم زیرا برای شرط ، اگر آرایه ها برابر باشند ، باید یک شرط انجام شود ، و این طول هر دو آرایه باید برابر باشد ، بنابراین وقتی طول هر دو آرایه را پیدا کردیم ، فقط باید بررسی کنیم که آیا برابر است یا نه ، اگر مساوی نیست ، ما فقط نادرست برمی گردانیم و نیازی به ادامه کار نداریم. اگر مشخص شد که برابر است ، فقط ما بیشتر جلو می رویم.

ما فرکانس های هر عنصر از آرایه 1 [] را در نقشه می شماریم و ذخیره می کنیم. فرض کنید دو یا سه بار یک عنصر واحد پیدا کردیم ، فقط فرکانس آن را 1 به روز کرده و افزایش می دهیم و در همان فرکانس همراه با آن عنصر ذخیره می کنیم.

مثال

اجازه بدین مثالی را مطرح کنیم:

arr1 [] = {1 ، 4 ، 2 ، 5 ، 2} ؛

arr2 [] = {2 ، 1 ، 5 ، 4 ، 2} ؛

پس از پیمایش آرایه 1 [] و قرار دادن همه عناصر با فرکانس های آنها در نقشه ، نقشه را به صورت زیر داریم.

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

همانطور که مقادیر موجود در نقشه خود را داریم ، باید آرایه دوم را رد کنیم و بررسی کنیم که آیا نقشه دارای عناصر array2 است یا خیر ، اگر شامل عناصر array2 [] نباشد ، نادرست برمی گردیم. ما بررسی خواهیم کرد که آیا فرکانس عنصر فعلی برابر با 0 است ، اگر درست تشخیص داده شود ، نادرست برمی گردانیم. سپس مقدار فرکانس عنصر فعلی را می گیریم و آن را به 1 کاهش می دهیم و دوباره مقدار را در نقشه قرار می دهیم. اگر همین تعداد بیش از یک بار وجود داشته باشد ، این برای دفعه بعدی کمک می کند. این شرط در آن مورد گنجانده شده است. وقتی از حلقه خارج شدیم ، به این معنی است که همه اعداد مشابه در آرایه را داریم و آرایه ها را برابر می کنیم. سپس ما درست باز خواهیم گشت.

همچنین مشاهده کنید
کوچکترین زیرآرایه با تعداد مجزا k

کد ++ 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 !!

کد جاوا برای بررسی مساوی بودن یا نبودن دو آرایه  

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) جایی که "n" تعداد عناصر آرایه است. استفاده از HashMap به ما امکان دستیابی به پیچیدگی زمان خطی را می داد در غیر این صورت زمان بسیار بیشتری می برد.

همچنین مشاهده کنید
حداکثر اختلاف بین شاخص های اول و آخر یک عنصر در آرایه

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. اگر همه عناصر مشخص باشند ، نقشه ما برای هر یک از اعداد ورودی مقدار کلیدی خواهد داشت. بنابراین پیچیدگی فضا نیز خطی است.