[리트코드][HARD] Median of Two Sorted Arrays

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

리트코드 Median of Two Sorted Arrays

문제 풀이 및 회고

문제가 굉장히 어려웠다. 2번까지는 생각이 다 났지만 시간복잡도를 O(log(m+n)) 이어야한다해서 생각이 나질 않았다.

코드(python)

풀이 1. 단순히 합치고 정렬하기

(시간복잡도: (m+n)O(log(m+n)))

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 합치고 (O(m+n))
        merged = nums1 + nums2

        # 정렬하기 (O(log(m+n)))
        merged.sort()

        total = len(merged)
        if total % 2 == 1:
            return merged[total//2]
        else:
            return (merged[total//2-1] + merged[total//2])/2

풀이 2. 중앙값이니까 두 리스트 원소를 하나씩 탐색하며 세기

(시간복잡도:O(m+n))

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        idx1, idx2 = 0, 0 # nums1 탐색 idx, nums2 탐색 idx
        result = 0

        mid1, mid2 = 0, 0 # 합쳐진 list가 짝수이면 중앙값은 두개 더 해야함
        for i in range((m+n)//2+1): # 중앙까지 찾기
            mid2 = mid1 # 이전 중앙값 할당
            if idx1 != m and idx2 != n: # 둘다 찾아보는 경우
                if nums1[idx1] < nums2[idx2]:
                    mid1 = nums1[idx1]
                    idx1 += 1
                else:
                    mid1 = nums2[idx2]
                    idx2 += 1
            elif idx1 != m: # idx2는 다 돌았음
                mid1 = nums1[idx1]
                idx1 += 1
            else:
                mid1 = nums2[idx2]
                idx2 += 1
        
        if (m+n)%2 == 1:
            return m1
        else:
            return (m1+m2)/2

풀이 3. Binary Search

문제에서 제시한 시간복잡도로 보아 리스트를 합치지 않고 이진 검색을 해야한다. 예를 들어 m개, n개의 리스트가 있다고 가정하자

$ [nums1[0], nums1[1], ... , nums[m-1]] [nums2[0], nums2[1], ... , nums[n-1]] $

이 두 리스트는 non-decrease 순으로 정렬되어 있기 때문에 두 리스트를 중앙값 대비 나눈다면

$ [nums1[0], nums1[1], ..., nums[a-1]| ... , nums[m-1]] [nums2[0], nums2[1], ..., nums[b-1]| ... , nums[n-1]] $

가 될 수 있다. 여기서 a+b개가 m+n개 중의 절반이므로 a+b = (m+n)//2가 성립한다.

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

        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)
        
        low, high = 0, m
        total = m+n

        while low <= high:
            mid1 = (low+high) // 2 # nums1에서 mid idx
            mid2 = (total+1)//2 - mid1 # nums2에서 mid idx

            l1 = nums1[mid1-1] if mid1-1 >= 0 else -float("inf") #mid에서 하나 왼쪽값 
            l2 = nums2[mid2-1] if mid2-1 >= 0 else -float("inf") 
            r1 = nums1[mid1] if mid1 < m else float("inf") # mid 값
            r2 = nums2[mid2] if mid2 < n else float("inf")
            
            if l1 <= r2 and l2 <= r1: # 만약 mid1의 L값(mid-1)이 mid2보다 작거나 같고, mid1 값이 mid2의 L값(mid-1)보다 작거나 같으면 알맞게 찾았음 해당 위치가 중앙값.
                if total %2 == 1:
                    return max(l1, l2)
                else:
                    return (max(l1, l2) + min(r1, r2))/2.0
            elif l1 > r2:
                high = mid1 - 1
            else:
                low = mid1 + 1
        
        return 0

혹은. 근데 아래 풀이는 merged = nums1 + nums2 일 때 시간복잡도가 O(m+n)인거로 아는데(아시는분 댓글 부탁바람) 가장 시간이 빠른 풀이라고 한다…

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        # Merge the arrays into a single sorted array.
        merged = nums1 + nums2

        # Sort the merged array.
        merged.sort()

        # Calculate the total number of elements in the merged array.
        total = len(merged)

        if total % 2 == 1:
            # If the total number of elements is odd, return the middle element as the median.
            return float(merged[total // 2])
        else:
            # If the total number of elements is even, calculate the average of the two middle elements as the median.
            middle1 = merged[total // 2 - 1]
            middle2 = merged[total // 2]
            return (float(middle1) + float(middle2)) / 2.0

궁금한 것들이나 추가 및 수정했으면 좋겠는 거 말해주시면 좋을 거 같아요. 좋은 하루 보내시길 바래요 :)