የሁለት ድርድሮች መቋረጥ II Leetcode Solution


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፌስቡክ google በ Oracle
ሃሽ ማፕ መደርደር ሁለት ጠቋሚዎች

የችግሩ መግለጫ

በዚህ ችግር ሁለት ድርድሮች ተሰጥተዋል እናም የዚህን ሁለት ድርድሮች መገናኛውን ፈልገን ማግኘት እና የውጤቱን ድርድር መመለስ አለብን ፡፡
በውጤቱ ውስጥ ያለው እያንዳንዱ ንጥረ ነገር በሁለቱም ድርድር ላይ እንደሚታየው ብዙ ጊዜ መታየት አለበት። ውጤቱ በማንኛውም ቅደም ተከተል ሊሆን ይችላል ፡፡

ለምሳሌ

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 ውስጥ የዚህ ቁጥር ቁጥር 1 ቁጥር አዎንታዊ ነው ወይም አለመሆኑን እንፈትሻለን።

  • ከተቆጠረ ቁጥር 2 [i] በድርድር ቁጥር 1 አዎንታዊ ነው ፣ ከዚያ ይህን ንጥረ ነገር ያክሉ (ቁጥር 2 [i]) በውጤት ድርድር እና በሃሽ ካርታ ውስጥ የዚህን ንጥረ ነገር ብዛት ይቀንሱ።
  • ካልሆነ ይህ ንጥረ ነገር በውጤቱ ውስጥ መጨመር የለበትም።

ማሳሰቢያ-የቦታውን ውስብስብነት ለመቀነስ መጠናቸው አነስተኛ በሆነ ሃሽ ካርታ ውስጥ የዚያ ድርድር ንጥረ ነገሮችን እናከማቻለን ፡፡

የሁለት መርከቦች መገንጠያ ትግበራ II Leetcode Solution

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 Leetcode Solution

የጊዜ ውስብስብነት

ኦ (n + m) N እና m የሰልፍ ርዝመት ሲሆኑ። በሁለቱም ድርድሮች በኩል ቀጥታ መስመር እንይዛለን እና በሃሽ ካርታ ውስጥ ለማስገባት እና ለማምጣት ሥራው የማያቋርጥ ጊዜ ይወስዳል ፡፡

የቦታ ውስብስብነት 

ኦ (ደቂቃ (n ፣ m)) የአነስተኛ ድርድር ክፍሎችን ለማከማቸት ሃሽ ካርታ እንጠቀማለን።

አቀራረብ 2 (ሁለት ጠቋሚዎችን በመጠቀም)

የሁለቱም ድርድር አካላት ከተደረደሩ ይህ አካሄድ ይበልጥ ቀልጣፋ ነው። እኛ ስለተደረደረ ለዚህ ችግር እኛ ዓይነት ሁለቱም ድርድሮች መጀመሪያ ፡፡
አሁን ለሁለቱ ድርድር ሁለት ጠቋሚዎችን i እና j እንጠቀማለን እና ሁለቱንም በዜሮ እንጀምራለን ፡፡
በ 1 ኛ ረድፍ ላይ መረጃ ጠቋሚውን ይውሰዱ (ቁጥር 1) እና ማውጫ j በ 2 ኛ ድርድር (ቁጥር 2)

  • I እና j የተጠቆሙትን ሁለቱን አካላት ያነፃፅሩ ፡፡
  • If ቁጥር 1 [i] ያንሳል ቁጥር 2 [j] ከዚያ የንጥረ ነገሮችን መገናኘት ለመፈተሽ አነስተኛውን ንጥረ ነገር ትተን ወደ ቁጥር (1) ድርድር ወደ ሚቀጥለው (ትልቁ) ንጥረ ነገር መሄድ እንዳለብን እናውቃለን።
  • ሌላ ከሆነ ቁጥር 1 [i] ይበልጣል ቁጥር 2 [j] ከዚያ በተመሳሳይ በቁጥር 2 ድርድር ውስጥ ወደ ቀጣዩ (ትልቁ) ንጥረ ነገር መሄድ አለብን።
  • ሌላ ሁለቱም ንጥረ ነገሮች ተገናኝተዋል ፣ ስለሆነም ይህን ንጥረ ነገር በድርድር ውጤት ይጨምሩ። እና ጭማሪ ሁለቱም i እና j.

ከዚህ በታች ባለው ስእል ምሳሌ በመጠቀም በዓይነ ሕሊናዎ እንዲታዩ ያስችልዎታል:

የሁለት ድርድሮች መቋረጥ II Leetcode Solution

 

የሁለት መርከቦች መገንጠያ ትግበራ II Leetcode Solution

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 Leetcode Solution

የጊዜ ውስብስብነት

ኦ (logn + logm): መጠናቸው n እና m የሆኑ ሁለቱን ድርድርዎች እናደርጋቸዋለን ፡፡ እና ከዚያ በሁለቱም ድርድሮች ላይ በመስመር ላይ እንሰጣለን ፡፡

የቦታ ውስብስብነት 

ኦ (ከፍተኛ (logn ፣ logm)) ወደ O (max (n, m)) እኛ የምንጠቀምበት ስልተ ቀመር በመለየት ላይ የተመሠረተ ነው ፡፡