4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

My Answer 1: Accepted (Runtime: 116 ms - 18.03% / Memory Usage: 14.6 MB - 59.04%)

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        lo = []
        hi = []
        
        for num1 in nums1:
            heappush(lo, -num1)             # lo is maxheap, so -1 * num
            heappush(hi, -lo[0])      # hi is minheap
            heappop(lo)

            if len(lo) < len(hi):
                heappush(lo, -hi[0])
                heappop(hi)
                
        for num2 in nums2:
            heappush(lo, -num2)             # lo is maxheap, so -1 * num
            heappush(hi, -lo[0])      # hi is minheap
            heappop(lo)

            if len(lo) < len(hi):
                heappush(lo, -hi[0])
                heappop(hi)
        
        if len(lo) > len(hi):
            return -lo[0]                  
        else:
            return (hi[0] - lo[0]) / 2  # - as low has -ve values

전에 풀었던 295. Find Median from Data Stream 의 min-heap, max-heap 응용함

num1 과 num2 를 합치고 정렬한 다음에 heap 에 넣으려다가 나름 런타임을 생각해서
(합치고 정렬하는게 좀 더 빠르긴 함...^^)

그냥 num1, num2 숫자 하나씩 넣는 걸로 했는데.. 이거도 O(log (m+n)) 은 안될듯...?

two pointer

Solution 1: Runtime: 92 ms - 71.36% / Memory Usage: 14.5 MB - 58.87%

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l1,l2 = len(nums1), len(nums2)
        middle = (l1 + l2) / 2
		
        # 둘 중 하나만 숫자가 있으면 => 있는 쪽의 nums[0] 을 리턴 (e.g. [1], [])
        if middle == 0.5: return float(nums1[0]) if l1 > l2 else float(nums2[0])
        
	# x 는 nums1 인덱스, y 는 nums2 인덱스를 나타냄
        x = y = 0
        cur = prev = 0
        # 총 길이가 짝수면 +1, 홀수면 +0.5
        loops = middle+1 if middle % 1 == 0 else middle+0.5
        
        # 최종적으로 cur 이 middle 을 가리키도록
        for _ in range(int(loops)):
            prev = cur	# prev 는 짝수의 평균 구할 때 이용
            # nums1 의 맨 끝까지 다 봤으면 nums2 나머지를 cur 로
            if x == l1:
                cur =  nums2[y]
                y += 1
            # nums2 의 맨 끝까지 다 봤으면 nums1 나머지를 cur 로
            elif y == l2:
                cur =  nums1[x]
                x += 1
            # 지금 보고 있는 nums1 과 nums2 값 중에 더 작은 값을 cur 로
            elif nums1[x] > nums2[y]:
                cur =  nums2[y]
                y += 1
            # nums1[x] <= nums2[y]
            else:
                cur =  nums1[x]
                x += 1
        
        # 짝수면 평균 구해서 return
        if middle % 1 == 0.0:
            return (cur+prev)/2
        # 홀수면 그냥 가운데 값 return
        else:
            return float(cur)

nums1 담당 x, nums2 담당 y 2개의 포인터 이용해서 median 값을 찾음

최종적으로 cur 이 middle 이 된다