[LeetCode] 350. Intersection of Two Arrays II - 문제풀이

Description

주어진 두 배열의 교집합으로 이루어진 배열을 반환하는 문제입니다.

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution 1. Using Array

public int[] intersect(int[] nums1, int[] nums2) {

    // 1. using array
    int[] map = new int[1001]; //각 value를 index(key)로 갯수 저장 >> 1 <= nums1.length, nums2.length <= 1000
    for(int num1 : nums1){
        map[num1]++;
    }
    // check intersection
    List<Integer> resultList = new ArrayList<>();
    for(int num2 : nums2){
        if(map[num2] > 0){ //교집합
            resultList.add(num2);
            map[num2]--;
        }
    }
    // convert List to Array        
    int[] result = new int[resultList.size()];
    for (int i = 0; i < resultList.size() ; i++) {
        result[i] = resultList.get(i);
    }
    return result;
}

Array를 이용해 각 value(1~1000)을 index로 하여 개수를 카운팅해줍니다. 그 이후 다른 배열 (nums2) 을 확인해 나가며 겹치는 값이 있을 경우 한 개씩 줄여나가면 교집합 목록에 추가합니다.

Solution 2. Using Hash Map

public int[] intersect2(int[] nums1, int[] nums2) {

    // 2. using Map
    Map<Integer,Integer> map = new HashMap<>(); //각 value를 index(key)로 갯수 저장
    for(int num1 : nums1){
        map.put(num1,map.getOrDefault(num1,0)+1);
    }
    // check intersection
    List<Integer> resultList = new ArrayList<>();
    for(int num2 : nums2){
        if(map.getOrDefault(num2,0) > 0){ //교집합
            resultList.add(num2);
            map.put(num2,map.get(num2)-1);
        }
    }
    // convert List to Array
    int[] result = new int[resultList.size()];
    for (int i = 0; i < resultList.size() ; i++) {
        result[i] = resultList.get(i);
    }
    return result;

}

Solution1과 유사하지만 Array대신 HashMap 클래스를 사용하여 map을 구성했습니다.

Reference

Intersection of Two Arrays II - LeetCode