[LeetCode] Median of Two Sorted Array

문제

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3] nums2 = [2] The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

 

Approach

O(log (m+n)) 만에 풀라는데 혹시나해서 그냥 두 배열 합쳐서 sorting하고 중간값 리턴했더니 통과는 하는데

이러면 O((m+n) + log(m+n))이므로 의도한 것보다 느리다

면접에서 이렇게 대답하면 더 빠른거 내놓으라고 할 것이 분명하다.

추가: Winner tree로 재구현

 

Optimization

LeetCode에는 Recursive Approach를 사용하라고 되어있음

Winner tree를 한번 써봐야겠음

추가: Winner tree로 구현했더니 확빨라 졌다 (상위 2%)

다른 답들을 보니 재귀 + binary search로 구현된 코드가 대다수

그리고 문제 조건에서 nums1과 nums2중 하나는 비었을 수 있었는데 놓치고 있었음

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_MedianOfTwoSortedArray.cpp

chi3236/algorithm

https://github.com/chi3236/algorithm/blob/master/LeetCode_MedianOfTwoSortedArrayWinnerTree.cpp

chi3236/algorithm