두 배열의 교차 II 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 (사용 해시 맵 

두 배열의 교차점을 찾으려면 (숫자1 숫자2) 먼저 한 배열의 각 요소 수를 저장할 수 있습니다 (let 숫자1) 해시 맵을 사용합니다. 그런 다음 두 번째 배열 (숫자2) nums2의 각 요소에 대해 nums1의 해당 요소 수가 양수인지 아닌지 확인합니다.

  • 카운트하면 nums2 [i] 배열 nums1이 양수이면 다음 요소를 추가하십시오 (nums2 [i])가 결과 배열에 있습니다. 그리고 해시 맵에서이 요소의 개수를 줄입니다.
  • 그렇지 않으면이 요소는 결과에 추가되지 않습니다.

참고 : 공간 복잡성을 최소화하기 위해 크기가 더 작은 해시 맵에 해당 배열의 요소를 저장합니다.

참조
파스칼 트라이앵글 Leetcode

두 어레이의 교차점 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]

자바 프로그램

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를 사용하고 둘 다 XNUMX으로 초기화합니다.
첫 번째 배열을 따라 인덱스 i 이동 (숫자1) 및 두 번째 배열 (숫자2)

  • i와 j가 가리키는 두 요소를 비교합니다.
  • If nums1 [i] ~보다 작다. nums2 [j] 그런 다음 요소의 교차를 확인하기 위해 더 작은 요소를 떠나 nums1 배열의 다음 (더 큰) 요소로 이동해야한다는 것을 알고 있습니다.
  • 그렇지 않으면 nums1 [i] 보다 큰 nums2 [j] 그런 다음 유사하게 nums2 배열의 next (greater) 요소로 이동해야합니다.
  • 그렇지 않으면 두 요소가 교차하므로이 요소를 결과 배열에 추가하십시오. 그리고 i와 j를 모두 증가시킵니다.
참조
문자열을 Leetcode 솔루션과 동일하게 만들기위한 최소 스왑

아래 그림의 예를 사용하여 시각화 해 보겠습니다.

두 배열의 교차 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]

자바 프로그램

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)) : 우리가 사용한 정렬 알고리즘에 따라 다릅니다.