Leetcode - Median of Two Sorted Arrays

Leetcode : Median of Two Sorted Arrays

Description

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

Output: 2.00000
// merged array = [1,2,3] and median is 2.

Example 2

Input

nums1 = [1,2], nums2 = [3,4]

Output

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

Example 3

Input

nums1 = [0,0], nums2 = [0,0]

Output

Output: 0.00000

Example 4

Input

nums1 = [], nums2 = [1]

Output

Output: 1.00000

Example 5

Input

nums1 = [2], nums2 = []

Output

Output: 2.00000

Approach

Although the problem asks for a median value of the merged sorted arrays - the problem requires more time on implementing efficient sorting algorithm

Solution (C++)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> merge = nums1;
        merge.insert(merge.end(), nums2.begin(), nums2.end());
        
        int mergeSize = merge.size();
        int half = mergeSize/2;
        
        double result;
        
        std::sort(merge.begin(), merge.end());
        
        if (mergeSize % 2 == 0)
            result = (merge[half] + merge[half - 1]) / 2.0;
        else
            result = (double)merge[half];
        
        return result;
    }
};

Result

Runtime: 96 ms
Memory Usage: 89.9 MB
Runtime Beats 11.09% of C++ Submission