[Leetcode(릿코드)] 349. Interserction of Two Arrays (Easy)

BinarySearch 문제

leetcode.com/problems/intersection-of-two-arrays/

Intersection of Two Arrays - LeetCode

---

문제

두 배열의 교집합을 구하는 문제이다

ex) nums1 = [1,2,2,1], num2= [2,2]

답은 [2]

해결

2가지 방식으로 풀었다

Runtime은  Set은 6~7ms / BinarySearch가 5ms 걸렸다

 

1. Set (O(n))

static int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> numSet1 = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
    Set<Integer> numSet2 = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
    Set<Integer> result = new HashSet<>();

    for (int num : numSet2) if (numSet1.contains(num)) result.add(num);
    return result.stream().mapToInt(x->x).toArray();
}

2. BinarySearch (O(nlogn))

static int[] intersection_binary(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Set<Integer> result = new HashSet<>();
    for (int num : nums2) if (binary_search(nums1, num)) result.add(num);
    return result.stream().mapToInt(x->x).toArray();
}

static boolean binary_search(int[] arr, int key) {
    int low = 0;
    int high = arr.length-1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = arr[mid];

        if (midVal < key) {
            low = mid+1;
        } else if (midVal > key) {
            high = mid-1;
        } else {
            return true;
        }
    }
    return false;
}