दुई एर्रे बराबर छ कि छैन जाँच गर्नुहोस्  


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एक्सेंचर Goldman सैक्स MAQ o9 समाधानहरू टैक्सी Sसुर 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. दुबै एर्रे को लम्बाई सेट गर्नुहोस् l1l2 क्रमशः।
  2. यदि दुबै लम्बाईहरू बराबर छैन भने जाँच गर्नुहोस्, ठीक भए, गलत फिर्ता।
  3. नक्सामा प्रत्येक तत्वको फ्रिक्वेन्सीहरू भण्डारण गर्नुहोस् र गणना गर्नुहोस्।
  4. दोस्रो एर्रे यात्रा गर्दै,
    1. जाँच गर्नुहोस् कि यदि नक्सा एआर २ तत्व समावेश गर्दैन, गलत फिर्ता।
    2. जाँच गर्नुहोस् कि विशेष तत्वको फ्रिक्वेन्सी ० बराबर छ यदि सहि छ भने गलत फिर्ता हुन्छ।
    3. वर्तमान तत्वको फ्रिक्वेन्सी १ द्वारा घटाउनुहोस्, यसलाई वर्तमान तत्वको फ्रिक्वेन्सीको ठाउँमा भण्डार गर्नुहोस्।
  5. Th चरण पुन: दोहोर्याउनुहोस् जब सम्म सबै मानहरू ट्र्यावर्स हुँदैनन्।
  6. साँचो फिर्ता

स्पष्टीकरण

हामीलाई एउटा समस्या दिइयो जुन पत्ता लगाउन को लागी दिइएको दुई एर्रे बराबर छन् कि छैनन् भनेर सोध्न। यसको समाधान गर्न हामी प्रयोग गर्न लागेका छौं ह्याशिंग, यसले हाम्रो समय बचत गर्न मद्दत गर्दछ र समय जटिलता कम गर्दछ।

पनि हेर्नुहोस्
मर्ज क्रमबद्ध गर्नुहोस्

हामीले गर्ने पहिलो चीज भनेको दुबै एर्रेको लम्बाइ पत्ता लगाउनु हो किनभने कन्डिसनको लागि यदि एरे बराबर छ भने एउटा सर्त पूरा गर्नु पर्छ, र त्यो हो एरेको लम्बाई बराबर हुनुपर्दछ, त्यसैले जब हामी दुबै एर्रेको लम्बाई भेट्छौं, हामीले जाँच गर्नु पर्छ कि बराबर छ कि छैन, यदि यो बराबर छैन भने हामी फर्कन्छौं र हामीलाई अगाडि बढ्नुपर्दैन। यदि यो बराबर पाइन्छ भने, हामी केवल अगाडि बढ्छौं।

हामी नक्शामा एर्रे १ [] को प्रत्येक तत्वको फ्रिक्वेन्सीहरू गणना र भण्डारण गर्दछौं। मानौं कि हामीले एकल तत्व दुई वा तीन पटक फेला पार्‍यौं, हामी यसको अपूर्णता १ लाई बढाउँदछौं र त्यहि आवृत्तिमा त्यस तत्वको साथ भण्डार गर्दछौं।

उदाहरणका

हामी एक उदाहरण विचार गरौं:

arr1 [] = {१,,, २,,, २};

arr2 [] = {१,,, २,,, २};

एर्रे १ ट्र्याव गरे पछि [] र सबै तत्वहरू उनीहरूको फ्रिक्वेन्सीको साथ नक्सामा राख्यौं हामीसँग नक्सा तल छ।

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

हामीसँग हाम्रो नक्सामा मानहरू छन्, हामीले दोस्रो एरे पार गर्नुपर्दछ र यदि नक्सामा एरे २ एलिमेन्टहरू छन् भने जाँच गर्नु पर्छ, यदि यसमा एरे २ [] एलिमेन्टहरू समावेश गरिएको छैन भने हामी गलत फिर्ता गर्छौं। हामी जाँच गर्नेछौं, यदि हालको एलिमेन्टको फ्रिक्वेन्सी ० बराबर छ, यदि यो सहि पाइएको छ भने हामी गलत फिर्ता गर्छौं। त्यसो भए हामी हालको एलिमेन्ट फ्रिक्वेन्सीको मान लिन्छौं र यसलाई १ बाट घटाउँछौं र मानलाई नक्शामा राख्छौं। त्यसो भए, यसले अर्को पटकको लागि मद्दत गर्दछ यदि समान संख्या एक पटक भन्दा बढीको लागि अवस्थित छ। यो अवस्था त्यो अवस्थामा सामेल छ। एक पटक हामी लूपबाट बाहिर आउँनेछौं, यसको मतलब हामीसँग एर्रेमा सबै समान अंक छन् र एरे बराबर हुनेछौं। त्यसो भए हामी सत्यमा फर्किनेछौं।

पनि हेर्नुहोस्
के डिस्टिंक्ट नम्बरहरूको साथ सब भन्दा सानो सुवाराय

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

जटिलता विश्लेषण  

समय जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। ह्यासम्यापको प्रयोगले हामीलाई रैखिक समय जटिलता प्राप्त गर्न अनुमति दिन्थ्यो अन्यथा यसले धेरै समय लिने थियो।

पनि हेर्नुहोस्
एर्रेमा एलिमेन्टको पहिलो र अन्तिम अनुक्रमणिका बीचमा अधिकतम भिन्नता

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। यदि सबै तत्वहरू भिन्न हुनेछन्, हाम्रो नक्सामा इनपुटमा प्रत्येक संख्याको लागि कुञ्जी-मान हुनेछ। यसैले अन्तरिक्ष जटिलता पनि रैखिक छ।