Median of Two Sorted Arrays

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

풀기 전

예전에 이미 풀어봤고 감명깊게 봤던 문제라서 잘 기억하고 있다.

이 문제는 log time에 풀어야 한다.

두 array를 merge하는 순간 O(n + m)의 시간복잡도가 발생해 로그타임에 풀 수가 없다.

sorted, log time → binary search 연상.

두 array의 길이를 각가 m,n이라고 하자.

두 array를 merge하면 길이가 (m+n)이 될것이다.

median은 (m+n)이 홀수인경우 (m+n)//2 번째 요소고

짝수인경우 (m+n)//2번째 요소와 (m+n)//2-1번째 요소의 평균값이다.

HALF_LENGTH = (m+n)//2 라고 하자.

두 array를 임의의 지점에서 잘랐을 때 각 쪼개진 array들의 길이가 n1, n2, m1, m2라고 하자.

이때 (n1+m1)가 (n2+m2)랑 같거나 1차이 난다면 n1,m1의 오른쪽 끝 값과 n2,m2의 왼쪽 끝 값들을 조사해서 두 array를 합쳤을 경우의 (m+n)//2번째 요소와 (m+n)//2-1번째 요소를 찾을 수 있다.

솔루션 학습

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        
        total_len = len(nums1) + len(nums2)
        half = total_len // 2
        low, high = 0, len(nums1) # 자를 지점이라서 len(nums1) 포함

        MIN = -10**6
        MAX = 10**6

        while low <= high:
            mid1 = (low + high) // 2
            mid2 = half - mid1

            # mid가 자르고 난뒤 오른쪽 array의 시작점

            left1 = nums1[mid1 - 1] if mid1 > 0 else MIN
            right1 = nums1[mid1] if mid1 < len(nums1) else MAX

            left2 = nums2[mid2 - 1] if mid2 > 0 else MIN
            right2 = nums2[mid2] if mid2 < len(nums2) else MAX

            if left1 > right2:
                high = mid1 - 1
            elif right1 < left2:
                low = mid1 + 1
            else:
                left_max = max(left1, left2)
                right_min = min(right1, right2)
                return right_min if total_len % 2 != 0 else (left_max + right_min) / 2

변수 초기화

        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        
        total_len = len(nums1) + len(nums2)
        half = total_len // 2
        low, high = 0, len(nums1) # 자를 지점이라서 len(nums1) 포함

        MIN = -10**6
        MAX = 10**6

if 문 : nums1이 nums2보다 짧음을 보장하기 위해 추가. 짧은 array를 정해놔야 구현도 편하고 이진탐색 시간복잡도도 줄어든다.
total_len : nums1과 nums2의 길이를 합친 것. 둘을 merge하면 총 길이가 얼마나 될까에 대한 답
half : total_len의 반
low, high : nums1을 이진탐색하기 위한 하한선과 상한선. mid값이 잘려진 array의 시작점이 될것이므로 len(nums1)도 포함해야함
MIN, MAX : array의 값으로 들어올 수 있는 최소값과 최대값

이진탐색

				while low <= high:
            mid1 = (low + high) // 2
            mid2 = half - mid1

            # mid가 자르고 난뒤 오른쪽 array의 시작점

            left1 = nums1[mid1 - 1] if mid1 > 0 else MIN
            right1 = nums1[mid1] if mid1 < len(nums1) else MAX

            left2 = nums2[mid2 - 1] if mid2 > 0 else MIN
            right2 = nums2[mid2] if mid2 < len(nums2) else MAX

nums1을 둘로 잘랐을 때 두 번째 array의 시작점 = mid1

nums2를 둘로 잘랐을 때 두 번째 array의 시작점 = mid2

left1 = 잘려진 nums1의 왼쪽 array의 max값

right1 = 잘려진 nums1의 오른쪽 array의 min값

left2 = 잘려진 nums2의 왼쪽 array의 max값

right2 = 잘려진 nums2의 오른쪽 array의 min값

판단

            if left1 > right2:
                high = mid1 - 1
            elif right1 < left2:
                low = mid1 + 1
            else:
                left_max = max(left1, left2)
                right_min = min(right1, right2)
                return right_min if total_len % 2 != 0 else (left_max + right_min) / 2

left1이 right2보다 작아야되는데 커버리면 좀더 작게 만들기 위해 high를 낮춤

right1이 left2보다 작은 경우는 그 반대로.

left1보다 right2가 크고 left2보다 right1이 크다면 잘 잘려진 것이므로 경계값을 이용해 median을 구한다.

분석

시간복잡도는 O(log(min(n, m)) (n = len(nums1), m = len(nums2))

공간복잡도는 O(1)