[leetcode 4] Median of Two Sorted Arrays

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

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

 

Example 1:

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000

 

문제 풀이:

난이도가 hard였지만 푸는 방법만 안다면 쉽게 풀수 있었다. 중요한건 두 배열을 merge하는 거였는데 모든 원소를 merge하는 거였다. 

merge sort에서 두 배열이 합쳐지는 로직을 사용했다. 투 포인터를 사용하여 각각의 배열에 시작점에 두고 하나씩 배열에 삽입.

 

중간값을 찾는 문제이므로 전체 배열이 홀수일 경우 중간위치에 있는 값을, 짝수일 경우 중간 위치의 2개의 평균을 리턴한다.

++#include <algorithm>에 merge라는 함수가 있었다.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> v;
        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = 0;
        
        while(left<m && right<n){

            if(nums1[left]<nums2[right]){
                
                v.push_back(nums1[left]);
                left++;
                
            }else {
                v.push_back(nums2[right]);
                right++;
            }
        }
        
        
        while(left<m){
            v.push_back(nums1[left]);
            left++;
        }
        
        while(right<n){
            v.push_back(nums2[right]);
            right++;
        }
        
        int len = v.size();
        
        if(len == 1){

            return v[0];
        }
        
        
        double answer=0;
        int mid = len/2;
   
        if(len % 2 == 0){
            answer = (double)(v[mid-1] + v[mid])/2;
          
        }else{
            answer = v[mid];
        }
        
        return answer;
    }
};