LeetCode: 4. Median of Two Sorted Arrays

개인적으론 정말 정말 어렵다...

아래 선생님께서 매우 친절하게 잘 알려주신다...

https://www.youtube.com/watch?v=LPFhl65R7ww&t=641s 

 

핵심을 정리하면 아래와 같다.

- nums1과 nums2 중 길이가 작은 리스트에 대해 binary search를 한다.

- nums1과 nums2를 partition 하되, nums1의 left partition과 nums2의 left partition은 전체 길이의 절반 혹은 절반 + 1이 되도록 partition한다. 즉, nums1의 partition p1이 결정되면, p2도 자동으로 결정된다. p2 = (m + n + 1) // 2 - p1

- p1이 0 혹은 m이 되는 경우의 corner case를 처리한다. p1이 0이라는 의미는 nums1에 left partition에 원소가 없다는 것이다. 이를 -INF로 처리한다. 반대로 p1이 m이라는 의미는 nums1의 right partition에 원소가 없다는 의미다. 이는 INF로 처리한다. p2도 이와 동일하게 처리해준다.

INF = int(1e9)
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        
        left, right, p = 0, m, (m+n+1) // 2
        while left <= right:
            p1 = (left + right) // 2
            p2 = p - p1
            
            maxleft1 = -INF if p1 == 0 else nums1[p1-1]
            minright1 = INF if p1 == m else nums1[p1]
            
            maxleft2 = -INF if p2 == 0 else nums2[p2-1]
            minright2 = INF if p2 == n else nums2[p2]
            
            if maxleft1 <= minright2 and maxleft2 <= minright1:
                if (m + n) % 2 == 0:
                    return (max(maxleft1, maxleft2) + min(minright1, minright2))/2.
                return max(maxleft1, maxleft2)
            
            elif maxleft1 > minright2:
                right = p1 - 1
            
            else:
                left = p1 + 1