Пересечение двух массивов II Решение Leetcode  


Сложный уровень Легко
Часто спрашивают в Амазонка Facebook Google Oracle
алгоритмы кодирование HashMap Интервью подготовка к собеседованию LeetCode LeetCodeSolutions Сортировка Два указателя

Постановка задачи  

В этой задаче два массивы даны, и мы должны найти пересечение этих двух массивов и вернуть результирующий массив.
Каждый элемент в результате должен появляться столько раз, сколько он отображается в обоих массивах. Результат может быть в любом порядке.

Пример

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

Подход 1 (Использование Хеш-карта 

Чтобы узнать пересечение двух массивов (nums1 и nums2) мы можем сначала сохранить количество каждого элемента одного массива (пусть nums1) с использованием хеш-карты. Затем мы можем пройти через второй массив (nums2) и для каждого элемента в nums2 мы проверяем, положительно ли количество этого элемента в nums1.

  • если количество nums2 [i] в массиве nums1 положительно, затем добавьте этот элемент (nums2 [i]) в массиве результатов. И уменьшите количество этого элемента на карте хэша.
  • иначе этот элемент не будет добавлен в результат.

Примечание: мы будем хранить элементы этого массива в хэш-карте, размер которой меньше, чтобы минимизировать сложность пространства.

Смотрите также
Leetcode треугольник Паскаля

Реализация решения Leetcode для пересечения двух массивов 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 Решение Leetcode

Сложность времени

О (п + м): Где n и m - длины массива. Мы выполняем линейную итерацию по обоим массивам, а операции вставки и выборки в хэш-карте занимают постоянное время.

Космическая сложность 

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

Подход 2 (с использованием двух указателей)  

Если элементы обоих массивов отсортированы, этот подход более эффективен. Для этой проблемы, поскольку она не решена, мы sort сначала оба массива.
Теперь мы будем использовать два указателя i и j для двух массивов и инициализировать оба нуля.
Переместите индекс i по 1-му массиву (nums1) и индекс j по 2-му массиву (nums2)

  • Сравните два элемента, обозначенные i и j.
  • If nums1 [i] меньше чем nums2 [j] тогда мы знаем, что нам нужно оставить меньший элемент и перейти к следующему (большему) элементу в массиве nums1, чтобы проверить пересечение элементов.
  • Иначе если nums1 [i] больше nums2 [j] затем аналогичным образом мы должны перейти к следующему (большему) элементу в массиве nums2.
  • В противном случае оба элемента пересекаются, поэтому добавьте этот элемент в массив результатов. И увеличить как i, так и j.
Смотрите также
Минимальные перестановки, чтобы сделать строки равными для решения Leetcode

Давайте визуализируем, используя пример на рисунке ниже:

Пересечение двух массивов II Решение Leetcodeшпилька

 

Реализация решения Leetcode для пересечения двух массивов 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 Решение Leetcode

Сложность времени

O (logn + logm): Мы сортируем оба массива размером n и m. Затем мы выполняем линейную итерацию по обоим массивам.

Космическая сложность 

От O (max (logn, logm)) до O (max (n, m)): Это зависит от используемого алгоритма сортировки.