4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

Median of Two Sorted Arrays - LeetCode

난이도: Hard

 

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.

 

처음으로 시간 복잡도에 대한 조건이 생겼다.

 

어떻게 중간값을 뽑아낼지 고민을 했는데,

두 배열을 정렬된 상태로 합치기만 하면 중간값은 가운데 인덱스일 것이다.

 

두 배열을 합친다는 것에서 merge sort가 생각났으나,

merge sort는 두 배열의 요소를 비교하며 새로운 배열에 집어넣는 과정에서 최대 n번의 비교가 행해진다.

따라서 O(m+n)의 시간 복잡도를 가질 것이다.

 

다른 방법을 찾던 중 이런 유튜브 영상을 발견했다.

https://www.youtube.com/watch?v=LPFhl65R7ww

 

약간의? 수학적 계산으로 O(log(min(m, n))의 시간 복잡도를 가질 수 있다.

두 배열을 각각 앞과 뒤 두 부분으로 잘라서,

앞 배열의 최댓값이 뒷 배열의 최솟값보다 작도록 교차해서 비교하는 방식이다.

말로 설명하긴 어려우나 영상을 보면 쉽게 이해할 수 있다.

(영상에서 첫 번째 예시의 end 값을 4로 시작했으나, 5로 시작해야 맞다.)

 

다음은 이를 기반으로 작성한 코드이다.

 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] shortArr = nums1;
        int[] longArr = nums2;
        
        if (shortArr.length > longArr.length) {
            shortArr = nums2;
            longArr = nums1;
        }
        
        final int HALF_TOTAL = (shortArr.length + longArr.length + 1) / 2;
        int shortLeftStart = 0;
        int shortLeftEnd = shortArr.length;
        int shortCutIdx, shortLeftMax, shortRightMin;
        int longCutIdx, longLeftMax, longRightMin;
        
        while (true) {
            shortCutIdx = (shortLeftStart + shortLeftEnd) / 2;
            longCutIdx = HALF_TOTAL - shortCutIdx;
            
            try {
                shortLeftMax = shortArr[shortCutIdx - 1];
            }
            catch (Exception e) {
                shortLeftMax = Integer.MIN_VALUE;
            }
            try {
                shortRightMin = shortArr[shortCutIdx];
            }
            catch (Exception e) {
                shortRightMin = Integer.MAX_VALUE;
            }
            try {
                longLeftMax = longArr[longCutIdx - 1];
            }
            catch (Exception e) {
                longLeftMax = Integer.MIN_VALUE;
            }
            try {
                longRightMin = longArr[longCutIdx];
            }
            catch (Exception e) {
                longRightMin = Integer.MAX_VALUE;
            }
            
            if (shortLeftMax > longRightMin) {
                // move left
                shortLeftEnd = shortCutIdx - 1;
            }
            else {
                if (longLeftMax > shortRightMin) {
                    // move right
                    shortLeftStart = shortCutIdx + 1;
                }
                else {
                    // correct
                    if ((shortArr.length + longArr.length) % 2 == 1) {
                        return Math.max(shortLeftMax, longLeftMax);
                    }
                    else {
                        return ((double)Math.max(shortLeftMax, longLeftMax) + Math.min(shortRightMin, longRightMin)) / 2;
                    }
                }
            }
        }
        
    }
}

 

혹자가 보면 욕할지도 모르겠다(....)

index 오류, 즉 두 개의 배열을 자르는 과정에서 잘린 한 쪽이 비어있을 때,

해당 부분의 최대/최소 값은 무한대로 정의해야 한다.

조건문 분기를 통하여 코드를 작성하려고 하니 같은 코드가 재사용되어,

어쩔 수 없이 try-catch문을 떡칠하여 일단 해결했다.

try-catch문은 수행 시간이 오래걸리는 단점이 있다고 하니 주의해야겠다.