4. Median of Two Sorted Arrays

数组中位数

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

大致意思：给定两个排好序的数组nums1和nums2，两个数组的大小分别为m和n，找出这两个数组的中位数。要求总体运行时间复杂度为：O(log(m+n))。

常规解法：因为两个数组都是有序的，可以对两个数组进行merge合并，合并完成后仍然是有序的。对合并完成后的数组长度进行判断，因为求的是中位数，如果是偶数取中间两个数字的平均数，如果是奇数，取中间的那个数。（下面第一个是自己实现merge算法）

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

其它解法：这个方法思想同上。只是这里的merge算法是用STL标准模板库的merge方法，效率应该会更高点。

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