בדוק אם שני מערכים שווים או לא  


רמת קושי בינוני
נשאל לעתים קרובות אקסנצ'ר גולדמן זאקס מאק פתרונות 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, החזר שקר.
    2. בדוק אם התדר של אותו אלמנט מסוים שווה ל- 0 אם נכון ואז החזר כוזב.
    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}

מכיוון שיש לנו את הערכים במפה שלנו, עלינו לחצות את המערך השני ולבדוק אם במפה יש אלמנטים של מערך 2, אם היא אינה מכילה את האלמנטים של מערך 2 [], אנו מחזירים שקר. נבדוק, אם תדירות האלמנט הנוכחי שווה ל- 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 !!

קוד 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) איפה "N" הוא מספר האלמנטים במערך. השימוש ב- HashMap אפשר לנו להשיג מורכבות זמן ליניארית אחרת זה היה לוקח הרבה יותר זמן.

ראה גם
ההבדל המרבי בין האינדקסים הראשונים והאחרונים של אלמנט במערך

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. אם כל האלמנטים יהיו מובחנים, למפה שלנו יהיה ערך מפתח לכל אחד מהמספרים בקלט. לפיכך מורכבות החלל היא גם לינארית.