दोन अ‍ॅरे समान आहेत की नाही ते तपासा


अडचण पातळी मध्यम
वारंवार विचारले ऐक्सचर गोल्डमन Sachs एमक्यू o9 सोल्यूशन्स टॅक्सी 4 सुअर 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. नकाशा यात एर 2 घटक नाहीत, चुकीचे परत या.
    2. त्या विशिष्ट घटकाची वारंवारिता 0 असल्यास बरोबर असल्याचे तपासा तर चुकीचे परत करा.
    3. वर्तमान घटकाची वारंवारिता 1 ने कमी करा, त्यास वर्तमान घटकाच्या वारंवारतेच्या त्या ठिकाणी ठेवा.
  5. सर्व मूल्ये आक्रमित होईपर्यंत चौथी पायरी पुन्हा करा.
  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 ने कमी करतो आणि पुन्हा मूल्य नकाशामध्ये ठेवतो. तर, हीच संख्या एकापेक्षा जास्त वेळा अस्तित्त्वात राहिल्यास हे पुढच्या वेळेस मदत करेल. या प्रकरणात या स्थितीचा समावेश आहे. एकदा आपण लूपमधून बाहेर आल्यावर त्याचा अर्थ असा आहे की आपल्याकडे अ‍ॅरे मधील सर्व संख्या समान आहेत आणि अ‍ॅरे समान करा. मग आपण सत्य परत करू.

दोन अ‍ॅरे समान आहेत की नाही हे तपासण्यासाठी सी ++ कोड

#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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. हॅशमॅप वापरण्यामुळे आम्हाला रेषात्मक वेळची जटिलता प्राप्त करण्याची अनुमती मिळाली नाहीतर यापेक्षा जास्त वेळ लागला असता.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. जर सर्व घटक वेगळे असतील तर आमच्या नकाशामध्ये इनपुटमधील प्रत्येक संख्येचे की-मूल्य असेल. अशा प्रकारे अवकाशातील अवघडपणा देखील रेषात्मक आहे.