Перасячэнне двух масіваў II рашэнне штрыхкода


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка facebook Google Аракул
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 рашэнне штрыхкода

Праграма 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 рашэнне штрыхкода

Складанасць часу

O (n + m): Дзе n і m - даўжыні масіва. Мы лінейна ітэруем па масівах, а ўстаўка і здабыча ў хэш-карце займае пастаянны час.

Касмічная складанасць 

O (мін (п, м)): Мы выкарыстоўваем хэш-карту для захоўвання элементаў меншага масіва.

Падыход 2 (з выкарыстаннем двух паказальнікаў)

Калі элементы абодвух масіваў адсартаваны, то гэты падыход больш эфектыўны. Па гэтай праблеме мы не сартуем сартаваць спачатку абодва масіва.
Цяпер мы будзем выкарыстоўваць два паказальнікі i і j для двух масіваў і ініцыялізаваць абодва нулём.
Перамясціць індэкс i ўздоўж 1-га масіва (нумары1) і індэкс j уздоўж 2-га масіва (нумары2)

  • Параўнайце два элементы, на якія паказваюць i і j.
  • If nums1 [i] менш nums2 [j] тады мы ведаем, што нам трэба пакінуць меншы элемент і перайсці да наступнага (большага) элемента ў масіве nums1, каб праверыць перасячэнне элементаў.
  • Інакш калі nums1 [i] больш nums2 [j] тады аналагічна мы павінны перайсці да наступнага (большага) элемента ў масіве nums2.
  • У іншым выпадку абодва элемента перасякаюцца, таму дадайце гэты элемент у масіў вынікаў. І павялічваць i і j.

Давайце візуалізуем на прыкладзе на малюнку ніжэй:

Перасячэнне двух масіваў II рашэнне штрыхкода

 

Рэалізацыя для перасячэння двух масіваў II рашэнне штрыхкода

Праграма 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 рашэнне штрыхкода

Складанасць часу

O (logn + logm): Мы сартуем абодва масівы, памер якіх роўны n і m. А потым мы лінейна ітэруем на абодвух масівах.

Касмічная складанасць 

Ад O (макс (logn, logm)) да O (макс (n, m)): Гэта залежыць ад алгарытму сартавання, які мы выкарыстоўвалі.