دو ارایوں II لیکٹ کوڈ حل کی باڑ لگانا


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون فیس بک گوگل اوریکل
ہش میپ چھانٹ دو اشارے

مسئلہ یہ بیان

اس مسئلہ میں دو صفیں دیئے گئے ہیں اور ہمیں اس دو صفوں کا چوراہا تلاش کرنا ہے اور نتیجہ سرنی کو واپس کرنا ہے۔
نتیجے میں ہر عنصر جتنی دفعہ ظاہر ہونا چاہئے وہ دونوں صفوں میں دکھاتا ہے۔ نتیجہ کسی بھی ترتیب میں ہوسکتا ہے۔

مثال کے طور پر

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

نقطہ نظر 1 (استعمال کرنا) ہیش کا نقشہ)

دو صفوں کا چوراہا معلوم کرنے کے لئے (نمبر 1 اور نمبر 2) ہم سب سے پہلے ایک صف کے ہر عنصر کی گنتی کو ذخیرہ کرسکتے ہیں نمبر 1) ایک ہیش نقشہ استعمال کرتے ہوئے۔ تب ہم دوسرے صف سے گزر سکتے ہیں (نمبر 2) اور نمبر 2 میں موجود ہر عنصر کے ل we ہم یہ چیک کریں گے کہ آیا نمبر 1 میں اس عنصر کی گنتی مثبت ہے یا نہیں۔

  • اگر گنتی ہے نمبر 2 [i] صف میں نمبر 1 مثبت ہے ، پھر اس عنصر کو شامل کریں (نمبر 2 [i]) نتیجہ سرنی میں۔ اور ہیش نقشہ میں اس عنصر کی گنتی کو کم کریں۔
  • بصورت دیگر اس عنصر کو شامل نہیں کیا جائے گا۔

نوٹ: ہم اس سرنی کے عناصر کو ہیش میپ میں محفوظ کریں گے جس کا سائز چھوٹا ہے تاکہ خلائی پیچیدگی کو کم سے کم کیا جاسکے۔

دو اراے II لیکٹ کوڈ حل کی تقویت کے لئے عمل درآمد

سی ++ پروگرام

#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): جہاں این اور ایم سرنی کی لمبائی ہیں۔ ہم دونوں صفوں کے ذریعے خطی طور پر اعادہ کرتے ہیں اور ہیش کے نقشے میں داخل اور بازیافت کا عمل مستقل وقت لگتا ہے۔

خلائی پیچیدگی 

O (منٹ (این ، ایم)): ہم چھوٹی سرنی کے عناصر کو ذخیرہ کرنے کے لئے ہیش میپ کا استعمال کرتے ہیں۔

نقطہ نظر 2 (دو پوائنٹس کا استعمال کرتے ہوئے)

اگر دونوں صفوں کے عناصر کو ترتیب دیا جائے تو یہ نقطہ نظر زیادہ موثر ہے۔ اس مسئلے کے ل as کیوں کہ اس کو حل نہیں کیا گیا ہے ترتیب دیں پہلے دونوں ارے۔
اب ہم دو صفوں کے ل two دو پوائنٹرز i اور j کا استعمال کریں گے اور دونوں کو صفر سے شروع کریں گے۔
پہلی صف کے ساتھ انڈیکس میں منتقل کریں (نمبر 1) اور دوسرا صف کے ساتھ انڈیکس جے (نمبر 2)

  • I اور j کی طرف اشارہ کردہ دو عناصر کا موازنہ کریں۔
  • If نمبر 1 [i] سے کم ہے نمبر 2 [j] تب ہم جانتے ہیں کہ ہمیں چھوٹا عنصر چھوڑنا ہے اور نمبر 1 صف میں اگلے (زیادہ) عنصر میں جانا ہے تاکہ عناصر کے چوراہے کی جانچ پڑتال کی جاسکے۔
  • ورنہ اگر نمبر 1 [i] سے بڑا ہے نمبر 2 [j] پھر اسی طرح ہمیں نمبر 2 صف میں اگلے (زیادہ) عنصر پر جانا ہے۔
  • باقی دونوں عناصر کو ایک دوسرے سے چوراہے ، لہذا اس عنصر کو نتیجہ سرنی میں شامل کریں۔ اور I اور j دونوں میں اضافہ۔

ذیل میں اعداد و شمار میں ایک مثال استعمال کرتے ہوئے تصور کرتے ہیں:

دو ارایوں II لیکٹ کوڈ حل کی باڑ لگانا

 

دو اراے II لیکٹ کوڈ حل کی تقویت کے لئے عمل درآمد

سی ++ پروگرام

#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 (لاگ ان + لاگم): ہم دونوں ارایوں کو ترتیب دیتے ہیں جن کا سائز ن اور ایم ہے۔ اور پھر ہم دونوں صفوں میں خطی طور پر تکرار کرتے ہیں۔

خلائی پیچیدگی 

O (زیادہ سے زیادہ (لاگ ان ، لاگم)) سے O (زیادہ سے زیادہ (ن ، م)): اس کا انحصار الگورتھم کی چھانٹ رہا ہے جو ہم استعمال کرتے ہیں۔