[LeetCode] 4. Median of Two Sorted Arrays (C++)

문제

두개의 정렬된 배열이 주어졌을 때, 두 배열의 중앙값을 리턴하기

• 이때, 시간복잡도가 O(log m+n)이 되도록 해야한다.
• 짝수일 경우에는 가운데 두개의 값의 평균을 출력해야 한다.

생각할 것

두개의 배열이 정렬되어 있으므로 한개씩 비교해보자.

그리고 시간복잡도에 log가 들어가 있으므로 절반만큼만 탐색할 것이다!

결과 코드

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double prev;
        double res;
        int idx1 = 0;
        int idx2 = 0;
        for(int i=0; i<=(nums1.size()+nums2.size())/2 ; i++){
            prev = res; 
            if(idx1 < nums1.size() && idx2 < nums2.size()){
                if(nums1[idx1] <= nums2[idx2]){                   
                    res = nums1[idx1];
                    idx1++;     
                } else {
                    res = nums2[idx2];
                    idx2++;
                }
            }
            else if(idx1 < nums1.size() && !(idx2 < nums2.size())){
                res = nums1[idx1];
                idx1++;
            }
            else if(!(idx1 < nums1.size()) && idx2 < nums2.size()){
                res = nums2[idx2];
                idx2++;
            }
        }
        
        if((nums1.size()+nums2.size())%2 == 0) {
            return (prev + res) / 2;
        }
        else {
            return res;
        }
    }
};

참고 사항

처음에 난이도만 보고 쫄았던 문제.

그래서 사실 문제를 풀고 첫번째 제출에 정답이라 당황했다…

앞으로도 문제를 풀기 전에 당황하지 말고 조건을 보며 차분히 생각하자!

그리고 이 기법이 Merge Sort를 이용한 것이라는 것을 알아두자~!