두 배열의 교차 II Leetcode 솔루션-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

차례

문제 정책

이 문제에서 두 배열 이 두 배열의 교차점을 찾아 결과 배열을 반환해야합니다.
결과의 각 요소는 두 배열에 표시되는 횟수만큼 나타나야합니다. 결과는 임의의 순서 일 수 있습니다.

예

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])가 결과 배열에 있습니다. 그리고 해시 맵에서이 요소의 개수를 줄입니다.
그렇지 않으면이 요소는 결과에 추가되지 않습니다.

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

두 어레이의 교차점 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를 모두 증가시킵니다.

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

핀