दो एरेस II लेटेकोड सॉल्यूशन का अंतर्ग्रहण  


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Facebook गूगल ओरेकल
एल्गोरिदम कोडिंग हैश मैप साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस छंटाई दो संकेत

समस्या का विवरण  

इस समस्या में दो सरणियों दिए गए हैं और हमें इस दो सरणियों के प्रतिच्छेदन का पता लगाना है और परिणामी सरणी को वापस करना है।
परिणाम में प्रत्येक तत्व को दोनों सरणियों में दिखाए गए अनुसार कई बार दिखाई देना चाहिए। परिणाम किसी भी क्रम में हो सकता है।

उदाहरण

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

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

दो सरणियों के प्रतिच्छेदन का पता लगाने के लिए (अंक १ और अंक १) हम पहले एक सरणी के प्रत्येक तत्व की गिनती को स्टोर कर सकते हैं (चलो अंक १) हैश मैप का उपयोग करना। तब हम दूसरे सरणी के माध्यम से पार कर सकते हैं (अंक १) और nums2 में प्रत्येक तत्व के लिए हम यह जांचेंगे कि अंक 1 में उस तत्व की गिनती सकारात्मक है या नहीं।

  • अगर की गिनती अंक 2 [i] सरणी में अंक 1 सकारात्मक है, फिर इस तत्व को जोड़ें (अंक 2 [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 लेटकोड सॉल्यूशन के अंतर के लिए जटिलता विश्लेषण

समय जटिलता

ओ (n + m): जहाँ n और m सरणी की लंबाई है। हम दोनों सरणियों के माध्यम से रैखिक रूप से पुनरावृत्ति करते हैं और हैश मानचित्र में सम्मिलित करते हैं और संचालन को स्थिर करते हैं।

अंतरिक्ष जटिलता 

O (न्यूनतम (n, m)): हम छोटे सरणी के तत्वों को संग्रहीत करने के लिए हैश मैप का उपयोग करते हैं।

दृष्टिकोण 2 (दो बिंदुओं का उपयोग करके)  

यदि दोनों सरणी के तत्वों को क्रमबद्ध किया जाता है तो यह दृष्टिकोण अधिक कुशल है। इस समस्या के लिए के रूप में यह हम हल नहीं है तरह पहले दोनों सरणियाँ।
अब हम दो बिंदुओं के लिए दो बिंदुओं i और j का उपयोग करेंगे और दोनों को शून्य से आरंभ करेंगे।
1 सरणी के साथ सूचकांक मैं ले जाएँ (अंक १) और 2 जी सरणी के साथ सूचकांक जे (अंक १)

  • I और j द्वारा बताए गए दो तत्वों की तुलना करें।
  • If अंक 1 [i] से कम है संख्या 2 [जे] तब हम जानते हैं कि हमें छोटे तत्व को छोड़ना होगा और अंक 1 सरणी में अगले (अधिक) तत्व पर जाना होगा ताकि तत्वों के प्रतिच्छेदन की जांच हो सके।
  • और अगर अंक 1 [i] से अधिक है संख्या 2 [जे] फिर इसी तरह हमें अंक 2 सरणी में अगले (अधिक) तत्व पर जाना है।
  • दोनों तत्वों को एक दूसरे से अलग करें, इसलिए इस तत्व को परिणाम सरणी में जोड़ें। और इंक्रीमेंट 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 (logn + logm): हम दोनों सरणियों को सॉर्ट करते हैं जिनका आकार n और m है। और फिर हम दोनों सरणियों पर रैखिक रूप से पुनरावृति करते हैं।

अंतरिक्ष जटिलता 

O (अधिकतम (logn, logm)) से O (अधिकतम (n, m)): यह हमारे द्वारा उपयोग किए गए एल्गोरिथ्म को सॉर्ट करने पर निर्भर करता है।