题目内容

给定两个大小分别为 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
$-10^6$ <= nums1[i], nums2[i] <= $10^6$

题解

首先需要明确，这里所指的中位数，在两个数组个数总和为奇数时，就是排序后的中位数，也是第k = (m+n)/2 的数。如果两个数组总和为偶数时，就是排序后最中间的两个数的平均数。

然后本题在思路上，采用递归的思想，将问题转化为子问题考虑，即：思考如何求解合并后的数组的第k小的数即可，因为中位数就是当k =（m+n)/2 的情况。

在方法上，有如下思考：
因为数组是正序，因此不用担心乱序的问题。
假设 m,n ≥ k/2。我们先从 nums1 和 nums2 中各取前 k/2 个元素（也就是看一下两个数组的前 k/2 个元素），有如下三种情况，这里详解一种情况，其他的就都会了。
1、nums1[k/2] < nums2[k/2]
当上述情况出现时，由于两个数组取出的数的个数一致，但因为nums1[k/2] 小于 nums2[k/2]，就会有nums2中取出来的数严格小于nums1[k/2]的数的数量小于k/2。因此，总共来看，小于nums1[k/2]的个数一定小于k。所以，在合并后，nums1[k/2]对应的数一定在第k个数之前。
所以，把nums1[k/2]的数之前的数全部删除，然后继续按照上述思路求解。

2、nums1[k/2] > nums2[k/2]
与上述思路一致，这里只不过删除nums2中的前k/2个元素

3、nums1[k/2] == nums2[k/2]
这里nums1[k/2]或者nums2[k/2]就是答案。

现在考虑边界情况，如果 m < k/2，则我们从 nums1 中取m个元素，从 nums2 中取 k/2 个元素（由于 k=(n+m)/2，因此 m,n 不可能同时小于 k/2.）

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if(total % 2 == 0){
            int left = find(nums1,0,nums2,0,total/2);
            int right = find(nums1,0,nums2,0,total/2+1);
            return (left + right) / 2.0;
        }else{
            return find(nums1,0,nums2,0,total/2+1);
        }

    }

    int find(vector<int>& nums1,int i,vector<int>& nums2,int j, int k){
        //i代表从nums1的第i个数开始，j代表从nums2的第j个数开始，k代表第k个数
        if(nums1.size() - i > nums2.size() - j) return find(nums2,j,nums1,i,k);//固定nums1较短，nums2较长
        
        //处理边界问题
        if(k == 1){
            if(nums1.size() == i){
                return nums2[j];
            }else{
                return min(nums1[i],nums2[j]);
            }
        }
        if(nums1.size() == i) return nums2[j+k-1];

        //
        int si = min((int)nums1.size(),i + k / 2), sj = j + k - k / 2;
        if(nums1[si - 1] > nums2[sj - 1]){
            return find(nums1,i,nums2,sj,k-(sj - j));
        }else{
            return find(nums1,si,nums2,j,k-(si - i));
        }
    }
};