LC4. Median of Two Sorted Arrays

작성일

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

  • 지난번에 요상하게 풀었던 두 정렬된 리스트에서 중앙값 찾기 문제
  • $O(log(n+m))$ 조건이 있어서 더 어렵다.
  • 지난번에는 양쪽에 번갈아가면 Binary Search를 하는 방식으로 $O(\log{n} \times \log{m})$ 로 풀었다.
  • 계속 고민하다가 결국 유튜브 보고 정해를 본 다음 품
  • 근데도 복잡해서 한참을 고민함
  • 포인트 몇가지
    • 일단 swap 해서 더 긴놈을 고정할것
    • 짧은 놈 기준으로 반을 나눈다음, 긴놈의 반도 전체가 절반이 되도록 나눔
    • 그러면 경계에 있는 2~4개의 수에서 중앙값이 나온다.
    • 이 문제는 수많은 경계조건이 나오는데 다 피하는게 진짜 욕나오게 짜증남..
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        cnt = len(nums1) + len(nums2)
        leftCnt = cnt//2
        rightCnt = cnt - leftCnt
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        if len(nums1) == 0:
            mid = len(nums2)//2
            if len(nums2)%2 == 0: return (nums2[mid-1] + nums2[mid]) / 2
            else: return float(nums2[mid])

        lb, ub = 0, len(nums1)+1
        while lb < ub:
            mid = (lb+ub)//2
            mid2 = leftCnt - mid
            a = nums1[mid-1] if mid != 0 else -0x3fffffff
            b = nums2[mid2] if mid2 != len(nums2) else 0x3fffffff
            if a >= b:
                ub = mid
            else:
                lb = mid + 1
        res = lb-1
        res2 = leftCnt - res
        arr = []
        if(res != 0): arr.append(nums1[res-1])
        if(res2 != 0): arr.append(nums2[res2-1])
        left = max(arr)
        arr = []
        if(res != len(nums1)): arr.append(nums1[res])
        if(res2 != len(nums2)): arr.append(nums2[res2])
        right = min(arr)
        if leftCnt == rightCnt: return (left+right)/2
        else: return right