[LeetCode] 4번 - Median of Two Sorted Arrays(두 정렬된 배열의 중앙값)

문제

4. Median of Two Sorted Arrays

Hard

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

풀이과정

(1)규칙

• 시간복잡도는 O(log (m+n)) 이어야만 합니다.
• num1, num2둘다 비어있지 않습니다.

(2)순서

num2의 요소를 num1에 이어붙이고, sort로 오름차순 정렬 해준 뒤

배열의 갯수가 짝수면 ( [배열길이/2-1]+[배열길이/2] ) / 2를 리턴, 홀수라면 [배열길이/2] 값을 리턴해줍니다.

(3)코드

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    nums1.insert(nums1.end(), nums2.begin(), nums2.end());//합치기
    sort(nums1.begin(), nums1.end());//정렬
 
    return (nums1.size() % 2 == 0) ?
        ((double)nums1[nums1.size() / 2 - 1] + (double)nums1[nums1.size() / 2]) / 2 :
        (double)nums1[nums1.size() / 2];
}
};

---

통과는 했지만 런타임속도나 메모리는 별로입니다. :(

솔루션에 나와있는 최적화된 버전을 이해하고 다시 수정하고 싶습니다.

---

[최적화된 버전]

(+20190727 Leet솔루션보다 더 이해하기 쉽게 설명한 블로그 링크를 첨부합니다)

https://medium.com/@hazemu/finding-the-median-of-2-sorted-arrays-in-logarithmic-time-1d3f2ecbeb46