İki Dizinin II Leetcode Həllinin kəsişməsi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Facebook google Kahin
alqoritmlər kodlaşdırma HashMap müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions çeşidləyici İki işarəBaxılıb 52

Problem bəyanat

Bu problemdə iki seriallar verilmişdir və bu iki massivin kəsişməsini öyrənməli və nəticələnən massivi qaytarmalıyıq.
Nəticədəki hər element hər iki massivdə göstərildiyi qədər görünməlidir. Nəticə istənilən qaydada ola bilər.

misal

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

Yanaşma 1 (istifadə olunur Xaş xəritəsi)

İki massivin kəsişməsini tapmaq üçün (nömrələr1 nömrələr2) əvvəlcə bir massivin hər elementinin sayını saxlaya bilərik (qoy nömrələr1) bir Hash xəritəsi istifadə edərək. Sonra ikinci sıra keçə bilərik (nömrələr2) və nums2-dəki hər bir element üçün nums1-də həmin elementin sayının müsbət olub olmadığını yoxlayardıq.

  • sayılırsa nums2 [i] array nums1 pozitivdir, sonra bu elementi əlavə edin (nums2 [i]) nəticə massivində. Və Hash xəritəsində bu elementin sayını azaldır.
  • əks halda bu element nəticəyə əlavə edilməməlidir.

Qeyd: həmin sıra elementlərini boşluq mürəkkəbliyini minimuma endirmək üçün ölçüsü daha kiçik olan hash map-də saxlayacağıq.

İki massivin kəsişməsi üçün tətbiqetmə II Leetcode həll

C ++ Proqramı

#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]

Java Proqramı

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]

İki massivin II Leetcode həllinin kəsişməsi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n + m): N və m serialın uzunluqlarıdır. Həm massivlərdən xətti olaraq təkrarlanır, həm də xaş xəritəsinə daxil etmə və gətirmə əməliyyatı sabit vaxt tələb edir.

Kosmik Mürəkkəblik 

O (dəq (n, m)): Kiçik massivin elementlərini saxlamaq üçün hash map istifadə edirik.

Yanaşma 2 (iki göstəricidən istifadə etməklə)

Hər iki massivin elementləri sıralanırsa, bu yanaşma daha səmərəlidir. Bu problem üçün biz sıralanmamışdır cür hər ikisi əvvəlcə.
İndi iki sıra üçün iki i və j göstəricilərindən istifadə edəcəyik və hər ikisini sıfırla işə salacağıq.
I indeksi 1-ci sıra boyunca hərəkət etdirin (nömrələr1) və 2-ci sıra boyunca j indeksi (nömrələr2)

  • İ və j ilə göstərilən iki elementi müqayisə edin.
  • If nums1 [i] azdır nums2 [j] onda bilirik ki, elementlərin kəsişməsini yoxlamaq üçün daha kiçik elementi tərk edib nums1 massivindəki növbəti (daha böyük) elementə getməliyik.
  • Digər halda nums1 [i] daha çox nums2 [j] o zaman eyni şəkildə nums2 massivindəki növbəti (daha böyük) elementə getməliyik.
  • Hər iki element də kəsişdi, nəticədə bu elementi nəticə massivinə əlavə edin. Və həm i, həm də artım.

Aşağıdakı şəkildə bir nümunə istifadə edərək görselləşdirək:

İki Dizinin II Leetcode Həllinin kəsişməsiPin

 

İki massivin kəsişməsi üçün tətbiqetmə II Leetcode həll

C ++ Proqramı

#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]

Java Proqramı

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]

İki massivin II Leetcode həllinin kəsişməsi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (logn + logm): Ölçüləri n və m olan hər iki massivi sıralayırıq. Və sonra hər iki massivdə də xətti olaraq təkrarlanırıq.

Kosmik Mürəkkəblik 

O (max (logn, logm)) ilə O (max (n, m)) arasında: Bu istifadə etdiyimiz çeşidləmə alqoritmindən asılıdır.

Şərh yaz

Translate »
1