LeetCode : 4. Median of Two Sorted Arrays

MergeSort(병합정렬)에서 처음에 Array가 쪼개지는 과정만 생략된 버전?이라고 할 수 있다.

 

[메인 로직]

즉, 정렬된 순서대로 2개의 Array를 합치는 과정을 통해 정렬된 하나의 Array를 만들고

합친 Array의 크기가 짝수라면 중간에 있는 2개의 값의 median값을 반환, 홀수라면 그냥 중간의 값을 반환하면 된다.

 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double ans = 0;
        vector<int> v;
        int i=0, j=0;
        while(i<nums1.size() && j<nums2.size()){
            if(nums1[i]<nums2[j]){
                v.push_back(nums1[i++]);
            }else{
                v.push_back(nums2[j++]);
            }
        }
        
        if(i<nums1.size()){
            while(i<nums1.size()){
                v.push_back(nums1[i++]);
            }
        }else{
            while(j<nums2.size()){
                v.push_back(nums2[j++]);
            }
        }
                
        int idx = v.size()/2;
        
        if(v.size()%2==0){
            ans = (double)(v[idx]+v[idx-1])/2;
        }else{
            ans = (double)v[idx];
        }
        
        return ans;
    }
};