LeetCode:寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

来源：力扣（LeetCode）
链接：(https://leetcode-cn.com/problems/median-of-two-sorted-arrays)

思路：

这道题目很容易想到先对两个数组进行排序，然后选取中位数，但是这样会额外需要O（m+n）空间，那有什么方法可以不用额外空间呢，思路其实和讲两个数组进行排序后再取中位数有异曲同工之处，我是否可以这样想，我们一刀是否能将两个数组切成两半，刚好使右边的数字都比左边的数字大且两边数量一致，那么我们这一刀上两边的数字就是我们需要的中间数字了，当两数组之和为偶数的时候，取左边最大的数、右边最小的数，再求平均就是我们的中位数了，当两数数组之和为奇数的时候，那就要看我们的切法是左边比右边多一个数字呢还是右边多一个数字，如果是左边多一个数字那么取左边最大的数字就是我们的中位数反之右边最小的数字就是我们的中位数了，请看下面的图解：

例1：两数组数目之和为偶数的时候

偶数时候的切割

解析：可以看得出来这一刀刚好将两个数组切为两个数量相等的部分，且右边的数字都比左边的大（只要是数组2切线左边最大的数字比数字1切线右边最小的数字小该条件或数组2切线右边最小的数字比数组1切线左边最大的数组大，都成立），我们取切线左边最大的数字8，再取切线右边最小的数字9，求平均（8+9）/2 = 8.5 刚好就是我们要的中位数。

例2：两数组数目之和为奇数的时候（这里我们的切法是使左边比右边多一个数）

奇数时候的切割

解析：可以看得出来这一刀刚好将两个数组切成左部分数目比右部分数目多一个，且右边的数字都比左边的大，我们这时候取切线左边最大的数字9，这个左部分最大的数字9刚好就是我们求的中位数。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> temp;
    int left,right,i,j;//left左边界 ,right边界 用于数组1的二分查找，i指向数组1元素的位置，j指向数组2元素的位置
    if (nums1.size()>nums2.size()) //这里为了让数组2的数量始终大于或等于数组1的数量（以防切割的时候数组2下没有元素，因为我们是遍历数组1来切割的) 
    { 
        temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }
    int m ,n, totalLeft;//totalLeft为切线数组1加上数组2左部分的数目
    m = nums1.size();
    n = nums2.size();
    left = 0;
    right = m;
    totalLeft = m + ((n - m) + 1) / 2; // (n+m+1)/2 的变式，这里加一是方便奇偶数统一运算
    while (left < right) 
    {
        i = left + (right - left) / 2;//二分查找 i为数组1查找的元素
        j = totalLeft - i; //那么j就一定要是切线左部分的数目减去数组1左部分的数目了
        if (nums2[j-1]>nums1[i])//如果数组2切线左边的数字大于数组1切线右边的数字，那么一定是数组1的数字不合适太小了
        {
            left = i+1;//左边界移至刚刚查找的地方，继续二分查找
        }
        else
        {
            right = i; //查找成功，将右边界至为i,退出二分查找
        }
    }
     i = left;//找到i的位置
     j = totalLeft - i;
    int nums1RightMin = i == m ? INT_MAX :nums1[i]; //这里需要考虑边界问题，如果找到的切线位于数组1最右端，那么使数组1右边最小值为最大值，这样就不会取到了
    int nums1LeftMax = i == 0 ? INT_MIN : nums1[i - 1];//如果找到的切线位于数组1最左端，那么使数组1左边最大值为最小值，这样就不会取到了
    int nums2RightMin = j == n ? INT_MAX : nums2[j];
    int nums2LeftMax = j == 0 ? INT_MIN : nums2[j - 1];
    if ((n+m)%2==1)
    {
        return (double)1.0*max(nums1LeftMax, nums2LeftMax) ; //如果两个数组数目之和为奇数，那么取数组1、数组2切线左边最大的值即可
    }
    else
    {
        return (double)1.0*(max(nums1LeftMax, nums2LeftMax)+ min(nums1RightMin,nums2RightMin))/2;//如果两个数组数目之和为偶数，那么取数组1、数组2切线左边最大的值与切线右边最小值得平均数
    }

}
int main() {
    vector<int> nums1, nums2;

    nums1.push_back(2);
    nums1.push_back(3);

    nums2.push_back(1);
    
    cout<<findMedianSortedArrays(nums1, nums2)<<endl;
    return 0;
}