இரண்டு வரிசைகள் II லீட்கோட் தீர்வின் குறுக்குவெட்டு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் கூகிள் ஆரக்கிள்
குறியீட்டு ஹாஷ்மேப் பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions வரிசையாக்க இரண்டு சுட்டிகள்

பொருளடக்கம்

சிக்கல் அறிக்கை  

இந்த சிக்கலில் இரண்டு வரிசைகள் வழங்கப்படுகின்றன, மேலும் இந்த இரண்டு வரிசைகளின் குறுக்குவெட்டைக் கண்டுபிடித்து அதன் விளைவாக வரிசையைத் தர வேண்டும்.
முடிவின் ஒவ்வொரு உறுப்பு இரு வரிசைகளிலும் காண்பிக்கும் பல மடங்கு தோன்றும். இதன் விளைவாக எந்த வரிசையிலும் இருக்கலாம்.

உதாரணமாக

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) மற்றும் nums2 இல் உள்ள ஒவ்வொரு உறுப்புக்கும் nums1 இல் உள்ள அந்த உறுப்பின் எண்ணிக்கை நேர்மறையானதா இல்லையா என்பதை நாங்கள் சோதிப்போம்.

  • எண்ணினால் nums2 [i] வரிசையில் nums1 நேர்மறையானது, பின்னர் இந்த உறுப்பைச் சேர்க்கவும் (nums2 [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): N மற்றும் m ஆகியவை வரிசையின் நீளம். நாங்கள் வரிசைகள் இரண்டின் மூலமும் நேர்கோட்டில் மீண்டும் செயல்படுகிறோம் மற்றும் ஹாஷ் வரைபடத்தில் செயல்பாட்டைச் செருகவும் பெறவும் நிலையான நேரம் எடுக்கும்.

விண்வெளி சிக்கலானது 

O (நிமிடம் (n, m)): சிறிய வரிசையின் கூறுகளை சேமிக்க ஹாஷ் வரைபடத்தைப் பயன்படுத்துகிறோம்.

அணுகுமுறை 2 (இரண்டு சுட்டிகளைப் பயன்படுத்துதல்)  

இரண்டு வரிசைகளின் கூறுகளும் வரிசைப்படுத்தப்பட்டால், இந்த அணுகுமுறை மிகவும் திறமையானது. இந்த சிக்கலுக்கு நாம் வரிசைப்படுத்தப்படவில்லை வகையான இரண்டு வரிசைகளும் முதலில்.
இப்போது நாம் இரண்டு வரிசைகளுக்கு i மற்றும் j ஆகிய இரண்டு சுட்டிகளைப் பயன்படுத்துவோம், இரண்டையும் பூஜ்ஜியத்துடன் துவக்குவோம்.
1 வது வரிசையில் குறியீட்டு i ஐ நகர்த்தவும் (எண் 1) மற்றும் குறியீட்டு j உடன் 2 வது வரிசை (எண் 2)

  • I மற்றும் j ஆல் சுட்டிக்காட்டப்பட்ட இரண்டு கூறுகளையும் ஒப்பிடுக.
  • If nums1 [i] விட குறைவாக உள்ளது nums2 [j] உறுப்புகளின் குறுக்குவெட்டுக்குச் சரிபார்க்க, சிறிய உறுப்பை விட்டுவிட்டு, எண் 1 வரிசையில் அடுத்த (அதிக) உறுப்புக்குச் செல்ல வேண்டும் என்பதை நாங்கள் அறிவோம்.
  • வேறு என்றால் nums1 [i] விட அதிகமாக உள்ளது nums2 [j] பின்னர் இதேபோல் நாம் nums2 வரிசையில் அடுத்த (அதிக) உறுப்புக்கு செல்ல வேண்டும்.
  • இரண்டு உறுப்புகளும் வெட்டப்படுகின்றன, எனவே இந்த உறுப்பை முடிவு வரிசைக்கு சேர்க்கவும். நான் மற்றும் ஜே இரண்டையும் அதிகப்படுத்துங்கள்.
மேலும் காண்க
சரங்களை சம லீட்கோட் தீர்வாக மாற்ற குறைந்தபட்ச பரிமாற்றங்கள்

கீழே உள்ள படத்தில் ஒரு எடுத்துக்காட்டைப் பயன்படுத்தி காட்சிப்படுத்தலாம்:

இரண்டு வரிசைகள் 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 (logn + logm): N மற்றும் m இன் அளவு இரண்டையும் வரிசைப்படுத்துகிறோம். பின்னர் இரண்டு வரிசைகளிலும் நேர்கோட்டுடன் மீண்டும் சொல்கிறோம்.

விண்வெளி சிக்கலானது 

O (அதிகபட்சம் (logn, logm)) to O (அதிகபட்சம் (n, m)): இது நாம் பயன்படுத்திய வழிமுறையை வரிசைப்படுத்துவதைப் பொறுத்தது.