दुई एर्रे II लेइटकोड समाधानको मिर्सो


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन फेसबुक गुगल बजेट
हशम्याप क्रमबद्ध दुई पोइन्टरहरू

समस्या वक्तव्य

यो समस्यामा दुई एर्रेहरू दिईएको छ र हामीले यो दुई एर्रेको छेदन पत्ता लगाउनु पर्छ र परिणाम एरे फिर्ता गर्नुपर्नेछ।
नतिजामा प्रत्येक तत्व धेरै चोटि देखा पर्दछ जुन दुबै एर्रेमा देखाइन्छ। परिणाम कुनै पनि क्रममा हुन सक्छ।

उदाहरणका

nums1 = [1,2,2,1], nums2 = [2,2]
[2,2]
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
[4,9]

दृष्टिकोण १ (प्रयोग गर्दै ह्यास नक्शा)

दुई एर्रेको छेदन पत्ता लगाउन (nums1 nums2) हामी पहिले एउटा एर्रेको प्रत्येक एलिमेन्टको गणनालाई भण्डार गर्न सक्छौं (मानौं nums1) ह्यास नक्शा प्रयोग गर्दै। त्यसो भए हामी दोस्रो एर्रेबाट पार गर्न सक्छौं (nums2) र nums2 मा प्रत्येक एलिमेन्टको लागि हामी जाँच गर्दछौं कि nums1 मा रहेको एलिमेन्टको गणना सकारात्मक छ वा छैन।

  • को गणना भने nums2 [i] एर्रे nums1 मा सकारात्मक छ, त्यसपछि यो तत्व थप्नुहोस् (nums2 [i]) परिणाम एर्रेमा। र ह्यास नक्शामा यस तत्वको गणना घटाउनुहोस्।
  • अन्यथा यस तत्व परिणाममा थप्न छैन।

नोट: हामी त्यो एर्रेको एलिमेन्ट्स ह्यास नक्शामा भण्डार गर्नेछौं जसको साइज सानो छ त्यसैले स्पेस जटिलता न्यूनतम बनाउन।

दुई एर्रे II लेटकोड समाधानको मिर्सोको लागि कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

    if(nums1.size()>nums2.size()){
        swap(nums1,nums2);
    }

    unordered_map< int , int >  m;
    for(auto val:nums1){
        m[val]++;
    }

    int k=0;
    for(auto val:nums2){
        if(m[val]>0){
            nums1[k++]=val;
            --m[val];
        }
    }

    return vector<int>(nums1.begin(),nums1.begin()+k);

}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

जावा कार्यक्रम

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        if(nums1.length>nums2.length){
            return intersect(nums2,nums1);
        }

        Map<Integer,Integer>  m= new HashMap<Integer,Integer>();
        for(int val:nums1){
            m.put(val,m.getOrDefault(val,0)+1);
        }

        int k=0;
        for(int val:nums2){
            if(m.getOrDefault(val,0)>0){
                nums1[k++]=val;
                m.put(val,m.get(val)-1);
            }
        }

        int ans[]=new int[k];
        for(int i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

दुई एर्रे II लेटकोड समाधानको प्रतिच्छेदनको लागि जटिलता विश्लेषण

समय जटिलता

O (n + m): जहाँ n र m एर्रेको लम्बाई हुन्छ। हामी दुबै एर्रे मार्फत linearly पुनरावृत्ति गर्दछौं र ह्यास नक्शामा सम्मिलित गर्दछौं र सञ्चालन ल्याउन स्थिर समय लिन्छ।

ठाउँ जटिलता 

O (min (n, m)): हामी सानो एर्रेको एलिमेन्टहरू भण्डार गर्न ह्यास नक्शा प्रयोग गर्दछौं।

दृष्टिकोण २ (दुई पोइन्टर्स प्रयोग गरेर)

यदि दुबै एर्रेको एलिमेन्ट्स क्रमबद्ध गरिएको छ भने यो दृष्टिकोण बढी सक्षम छ। यस समस्याको लागि यो क्रमबद्ध गरिएको छैन भाग्य दुबै एर्रे पहिले।
अब हामी दुई एर्रेको लागि दुई पोइन्टर i र j प्रयोग गर्नेछौं र दुबै शून्यबाट आरम्भ गर्नेछौं।
पहिलो अनुक्रमको साथ अनुक्रमणिका I सार्नुहोस् (nums1) र २ एरेमा अनुक्रमणिका jnums2)

  • दुई र तत्वहरू तुलना गर्नुहोस् I र j द्वारा।
  • If nums1 [i] भन्दा कम छ nums2 [j] त्यसोभए हामी जान्दछौं कि हामीले सानो एलिमेन्ट छोड्नुपर्नेछ र अर्को (ठूलो) एलिमेन्टमा nums1 एर्रेमा जानुपर्छ ताकि एलिमेन्ट्सको छेदन जाँच गर्न।
  • अरू भने nums1 [i] भन्दा ठूलो छ nums2 [j] त्यसो भए हामीले पनि अर्को (ठूलो) एलिमेन्टमा nums2 एर्रेमा जानु पर्ने हुन्छ।
  • अन्य दुबै तत्वहरू काण्डिएको, यसैले एरेमेन्ट एरेमा एरेमेन्ट गर्नुहोस् र I र j दुबै वृद्धि गर्दछ।

तल चित्रमा उदाहरण प्रयोग गरेर भिजुअलाइज गर्न दिन्छ:

दुई एर्रे II लेइटकोड समाधानको मिर्सो

 

दुई एर्रे II लेटकोड समाधानको मिर्सोको लागि कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
{
    sort(nums1.begin(),nums1.end());
    sort(nums2.begin(),nums2.end());

    int i=0,j=0,k=0;
    while(i<nums1.size() && j<nums2.size())
    {
        if(nums1[i]<nums2[j]) i++;
        else if(nums1[i]>nums2[j]) j++;
        else{
            nums1[k++]=nums1[i];
            ++i,++j;
        }
    }

    return vector<int>(nums1.begin(),nums1.begin()+k);
}

int main() 
{
    vector<int> nums1={1,2,2,1};
    vector<int> nums2={2,2};
    vector<int> ans=intersect(nums1,nums2);
    for(int x:ans)
        cout<<x<<" ";
   return 0; 
}
[2,2]

जावा कार्यक्रम

import java.util.*;
class Rextester{
    
    public static int[] intersect(int[] nums1, int[] nums2)
    {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i=0,j=0,k=0;
        while(i<nums1.length && j<nums2.length)
        {
            if(nums1[i]<nums2[j]) i++;
            else if(nums1[i]>nums2[j]) j++;
            else{
                nums1[k++]=nums1[i];
                ++i;++j;
            }
        }
        
        int ans[]=new int[k];
        for(i=0;i<k;i++){
            ans[i]=nums1[i];
        }

        return ans;    
    }
    
  public static void main(String args[])
    {
        int[] nums1={1,2,2,1};
        int[] nums2={2,2};
    int[] ans=intersect(nums1,nums2);
        for(int x:ans)
            System.out.print(x+" ");
    }
}
[2,2]

दुई एर्रे II लेटकोड समाधानको प्रतिच्छेदनको लागि जटिलता विश्लेषण

समय जटिलता

O (लग इन + लगम): हामी दुबै एर्रे क्रमबद्ध गर्दछौं जसको आकार एन र मिटर हो। र हामी दुबै एर्रेमा linearly पुनरावृत्ति गर्छौं।

ठाउँ जटिलता 

O (अधिकतम (लगइन, लगम)) बाट O (अधिकतम (n, m)): यो हामीले प्रयोग गर्ने एल्गोरिथ्म क्रमबद्धमा निर्भर गर्दछ।