[Python/파이썬] LeetCode 4번 Median of Two Sorted Arrays

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

코드 (이분탐색)

class Solution:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        n = len(nums1)
        m = len(nums2)

        if n > m:
            return self.findMedianSortedArrays(nums2, nums1)

        left, right = 0, n
        while left <= right:
            partition1 = (left+right)//2
            partition2 = (n+m+1)//2 - partition1

            max1 = float('-inf') if partition1 == 0 else nums1[partition1-1]
            min1 = float('inf') if partition1 == n else nums1[partition1]

            max2 = float('-inf') if partition2 == 0 else nums2[partition2-1]
            min2 = float('inf') if partition2 == m else nums2[partition2]

            if max1 <= min2 and max2 <= min1:
                if (n+m) % 2 == 0:
                    return (max(max1, max2)+min(min1, min2))/2
                else:
                    return max(max1, max2)
            elif max1 > min2:
                right = partition1-1
            else:
                left = partition1+1

 

이분탐색을 어떻게 사용해야 할지 감이 잘 안 왔는데 아래의 블로그를 보고 도움을 얻었다.

Leetcode 4번 문제 풀이

두 개의 정렬을 각각 나누는 점을 찾는다는 아이디어가 참신했다.

 

코드 (정렬)

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

        # return the median of the two sorted arrays.
        merged_nums = sorted(nums1+nums2)
        total_len = n+m

        if (total_len) % 2 == 1:
            return merged_nums[total_len//2]
        else:
            return (merged_nums[total_len//2-1]+merged_nums[total_len//2])/2

 

처음에는 이렇게 풀었다.

 

근데 생각해보니 이건 시간 복잡도가 `O((m+n)log(m+n))`이므로 문제의 조건을 만족하지 않을 것 같아서 다른 방법을 찾아보니 이분탐색을 이용하는 방법이 있어서 결국 위의 방법으로 다시 풀었다.

 

정렬 시간 복잡도 참고 자료(timsort): https://d2.naver.com/helloworld/0315536

---

리트코드는 처음 써봤는데 생각보다는 괜찮다

시간과 메모리 측면에서 전체 제출 코드 중 상위 몇 퍼센트에 들어가는지 이렇게 띄워주는 기능이 좋은거 같다. 

이거 보고 Accepted된 코드도 백분위 안 나오면 다시 풀어보면 좋을듯