004.md

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)).

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

The median is 2.0

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

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

思路：

   1 如果两个数组都为空,直接返回0。    2 求出两个数组的长度，相加记为len，flag = len&1,得出总长度的奇偶属性。flag==1 表示len为奇数，flag==0表示len为偶数，记mid=len/2。 如果其中一个数组的长度为0，则返回另外一个数组的中间值，奇数返回下标为mid的值，偶数返回mid 和 mid-1表示的值。    3 使用两个下标i，j对应nums1，nums2.较小者存入新的数组nums3，然后对应更新i,j。因为只需要两个值,mid的值和mid-1的值，所以满足i+j<=mid即可。 i和j都表示检测对应数组对应的值，而还没有加入nums3。对于奇数而言nums3[mid]表示的是中间值，偶数而言nums3[mid]和nums3[mid]表示 中间值，所以一共需要mid个数，所以i+j<=mid。 且i<nums1.size(),j<nums2.size(). 4 根据flag返回nums3对应的值就可以了。

其他：对于一个数组arr而言(下标0开始)， 当长度为奇数的时候 mid = arr.size()/2.表示的是中间的值。当长度为偶数的时候 mid = arr.size()/2表示

   中间两个数的后一个。

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums3;
        int sz1 = nums1.size();
        int sz2 = nums2.size();
        int len = sz1+sz2;//总的长度
        int flag = len & 1; //判断奇偶 奇数flag=1，偶数flag=0
        int mid = len/2;//中间下标
        //总的长度为0
        if(len == 0) return 0;
        
        //其中一个数组的长度为0
        if(sz2==0 && flag==1){
            return nums1[mid];
        }else if(sz2==0 && flag==0){
            return (double)(nums1[mid] + nums1[mid-1])/2;
        }
        if(sz1==0 && flag==1){
            return nums2[mid];
        }else if(sz1==0 && flag==0){
            return (double)(nums2[mid] + nums2[mid-1])/2;
        }

        //两个数组的长度都不为0
        int i=0,j=0;//对应nums1和nums2的下标
        while(i < sz1 && j < sz2 && i+j <= mid){
            if(nums1[i]>=nums2[j]){
                 nums3.push_back(nums2[j++]);
            }else{
                 nums3.push_back(nums1[i++]);
            }

        }
        
        //如果i+j!=mid,将下标没有超出对应长度的数组的剩余数push_back直到i+j==mid
        if(i==sz1){
            while(i+j <= mid){
                nums3.push_back(nums2[j++]);
            }
        }else if(j==sz2){
            while(i+j <= mid){
                nums3.push_back(nums1[i++]);
            }
        }
        
        //根据奇偶返回对应值。
        if(flag==1) return nums3[mid];
        else return (double)(nums3[mid]+nums3[mid-1])/2;

    }
};