Екі массивтің қиылысы II Leetcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Facebook Google Oracle
HashMap Сұрыптау Екі нұсқағыш

Проблемалық мәлімдеме

Бұл мәселеде екі массивтер берілген және біз осы екі массивтің қиылысын анықтап, нәтижелік жиымды қайтаруымыз керек.
Нәтижедегі әр элемент екі массивте қанша көрінсе, сонша рет пайда болуы керек. Нәтиже кез-келген тәртіпте болуы мүмкін.

мысал

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 Leetcode шешімі

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]

Java бағдарламасы

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 шешімі

Уақыттың күрделілігі

O (n + m): Мұндағы n және m - массивтің ұзындықтары. Біз массивтер арқылы сызықтық түрде қайталаймыз және хэш-картаға кірістіру мен алу жұмысы тұрақты уақытты алады.

Ғарыштың күрделілігі 

O (мин (n, m)): Біз кіші массивтің элементтерін сақтау үшін хэш картасын қолданамыз.

2-тәсіл (екі нұсқағышты пайдалану)

Егер екі жиымның элементтері сұрыпталған болса, онда бұл тәсіл тиімдірек болады. Бұл мәселе үшін біз сұрыпталмағандықтан сорт алдымен массивтер.
Енді біз екі массив үшін екі i және j көрсеткіштерін қолданамыз және екеуін де нөлге теңестіреміз.
І индексін 1 массив бойымен жылжыту (сан 1) және 2 массив бойымен j индексі (сан 2)

  • I мен j белгілері көрсетілген екі элементті салыстырыңыз.
  • If nums1 [i] аз nums2 [j] сонда біз элементтердің қиылысуын тексеру үшін кіші элементті тастап, nums1 массивіндегі келесі (үлкен) элементке өту керек екенін білеміз.
  • Егер басқаша болса nums1 [i] қарағанда үлкен nums2 [j] содан кейін nums2 массивіндегі келесі (үлкен) элементке өту керек.
  • Басқа элементтердің екеуі де қиылысады, демек бұл элементті нәтижелер массивіне қосыңыз. Және i мен j-ді көбейтіңіз.

Төмендегі суреттегі мысалды пайдаланып көрнекі түрде көрейік:

Екі массивтің қиылысы II Leetcode шешімі

 

Екі массивтің қиылысуын жүзеге асыру II Leetcode шешімі

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]

Java бағдарламасы

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 шешімі

Уақыттың күрделілігі

O (logn + logm): Көлемі n және m болатын массивтердің екеуін де сұрыптаймыз. Содан кейін біз екі массивте де сызықтық түрде қайталаймыз.

Ғарыштың күрделілігі 

O (max (logn, logm)) to O (max (n, m)) дейін: Бұл біз қолданған сұрыптау алгоритміне байланысты.