[LeetCode] 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

Median of Two Sorted Arrays - LeetCode

문제 유형 : 정렬

문제 난이도 : Hard

 

문제

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

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

 

두 정렬된 배열 nums1과 nums2가 각각 m과 n의 개수를 가지고 있을 때, 두 정렬된 배열에서 중앙값을 구해라.

(두 배열 통틀어서 중앙값을 구해라)

 

 

풀이

두 배열을 합치고 정렬해준 뒤, 길이가 홀수이면 가운데 인덱스에 있는 값을 리턴해주면 되고,

짝수이면 중앙의 두 값의 평균을 구한다.

 

코드(C++)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> v;
        v.insert(v.end(), nums1.begin(), nums1.end());
        v.insert(v.end(), nums2.begin(), nums2.end());

        sort(v.begin(), v.end());

        if (v.size() % 2 == 1) {
            return v.at(v.size() / 2);
        }

        return (v.at(v.size() / 2 - 1) + v.at(v.size() / 2)) / 2.0;
    }
};