LeetCode 350. Intersection of Two Arrays II 자바 문제 풀이

문제 설명

• 문제: https://leetcode.com/problems/intersection-of-two-arrays-ii/description
• 설명: 두 개의 배열 nums1과 nums2에서 중복되는 숫자를 찾아내는 문제입니다.

접근 방식

• 아이디어: 각 배열의 숫자들을 HashMap을 사용하여 카운트하여 중복을 체크합니다. 이 문제의 함정은 각 배열에 중복되는 숫자가 존재할수 있다는 것입니다. 이미 정렬되어 있지 않다면, 두 포인터 를 이용해서 중복을 확인하는 방법은 비효율적입니다. 그러므로, 해시맵을 사용하여 중복숫자를 확인합니다
• 알고리즘:
  1. 먼저 nums1 배열의 각 숫자를 HashMap에 넣어 그 숫자의 출현 빈도를 카운트합니다.
  2. 다음으로 nums2 배열을 순회하면서, 해당 숫자가 HashMap에 있는지 확인하고, 빈도가 0보다 크면 결과 리스트에 추가하고 해당 숫자의 빈도를 줄입니다.

코드

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();

        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        for (int val : nums1) {
            map.put(val, map.getOrDefault(val, 0) + 1);
        }

        for (int val : nums2) {
            if (map.getOrDefault(val, 0) > 0) {
                result.add(val);
                map.put(val, map.getOrDefault(val, 0) - 1);
            }
        }

        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }
        return resultArray;
    }
}

결론

• 시간 복잡도: 이 알고리즘은 두 배열을 각각 한 번씩 순회하므로 O(m + n)입니다 (m은 nums1의 길이, n은 nums2의 길이).
• 공간 복잡도: HashMap에 각 숫자의 빈도를 저장하므로 O(min(m, n))입니다 (m과 n 중 더 작은 값을 사용).