4. Median of Two Sorted Arrays

[zeikar]

Problem link

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

Problem Summary

두 정렬된 배열을 합쳤을 때의 중앙값을 구하는 문제.

Solution

이건 쉬워 보이는데 구현이 생각보다 빡세서 로이형의 도움을 많이 받았다.

먼저 기본적인 아이디어는 이진 탐색인데, 한 리스트를 잡고 그 리스트에 대해 이진 탐색을 진행하면서 중앙값을 찾는 방식이다.
한 리스트의 지점을 골랐다면 중앙값은 중앙에 있는 값이므로 다른 리스트의 지점도 자동으로 선택되는 걸 이용한다. 따라서 선택하는 리스트는 사이즈가 다른 리스트보다 작아야 한다.

자세한 영상은 유튜브 참고 (https://youtu.be/LPFhl65R7ww)

<iframe width="560" height="315" src="https://www.youtube.com/embed/LPFhl65R7ww" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

Source Code

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        nums1 = [-9999999] + nums1 + [9999999]
        nums2 = [-9999999] + nums2 + [9999999]

        low = 0
        high = len(nums1)

        while low <= high:
            partition_x = (low + high) // 2
            partition_y = (len(nums1) + len(nums2) + 1) // 2 - partition_x

            max_left_x = nums1[max(0, partition_x - 1)]
            min_right_x = nums1[min(len(nums1) - 1, partition_x)]
            max_left_y = nums2[max(0, partition_y - 1)]
            min_right_y = nums2[min(len(nums2) - 1, partition_y)]

            if max_left_x <= min_right_y and min_right_x >= max_left_y:
                if (len(nums1) + len(nums2)) % 2 == 0:
                    return (max(max_left_x, max_left_y) + min(min_right_x, min_right_y)) / 2
                else:
                    return max(max_left_x, max_left_y)

            if min_right_x < max_left_y:
                low = partition_x + 1
            else:
                high = partition_x - 1

        return 0.0