[LeetCode 풀이/python] 4. Median of Two Sorted Arrays (hard)

문제 설명: 각각 크기 m, n 인 정렬된 두 개의 배열 nums1, num2 이 주어졌을 때, 두 배열의 중간값을 구하시오.

# 추가: 전체 실행의 시간 복잡도는 O(log (m+n)) 을 만족해야 함.

(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)))

 

예시 1)

입력: nums1 = [1,3], num2 = [2]  --> 출력: 2.0000

설명: 두 배열을 병합하여 만든 배열 [1,2,3] 의 중간값은 2.

 

예시 2)

입력: nums1 = [1,2], num2 = [3,4]  --> 출력: 2.5000

설명: 병합된 배열 = [1,2,3,4] 의 중간값은 (2 + 3) / 2 = 2.5.

 

예시 3)

입력: nums1 = [0,0], num2 = [0,0]  --> 출력: 0.0000

 

예시 4)

입력: nums1 = [], num2 = [1]  --> 출력: 1.0000

 

예시 5)

입력: nums1 = [2], num2 = []  --> 출력: 2.0000

 

제한 조건:

• nums1.length == m  &   nums2.length == n
• 0 <= m <= 1000  &  0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

 

 

 

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • merge sort 의 merge 연산을 활용!
    -- 이미 두 배열이 sorted array 이므로 이들을 merged (sorted) array 로 만드는데 드는 비용은 O(n)
  • merge 함수를 통해 merged array 만 구하면, 해당 배열의 길이가 홀 / 짝일 때 구분하여 각각에 대해 중간값 리턴

 

• 코드 구현

def merge(nums1, nums2):
    m = []
    i1, i2 = 0, 0

    while (i1 < len(nums1)) and (i2 < len(nums2)):
        if nums1[i1] <= nums2[i2]:
            m.append(nums1[i1])
            i1 += 1
        else:
            m.append(nums2[i2])
            i2 += 1
    
    if (i1 < len(nums1)):
        m.extend(nums1[i1:])
    elif (i2 < len(nums2)):
        m.extend(nums2[i2:])

    return m
    
def findMedianSortedArrays(nums1, nums2):
    merged = merge(nums1, nums2)
    idx, odd = divmod(len(merged),2)
        
    if odd:
        return merged[idx]
    else:
        return (merged[idx-1] + merged[idx])/2

 

• 결과
  • 테스트 케이스 다 통과는 했는데 생각해보니 시간 복잡도 O(log(m+n)) 이 아니라 O(n) ... (근데 통과시켜주네...?)
  • Discussions 에서 다른 풀이들 훑어보니 Binary Search 를 이용한다거나 하는 듯  -->  참고해서 시간 복잡도 O(log(m+n)) 수준으로 낮춘 알고리즘으로도 풀어볼 것!