这道题很有意思，题目是给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数，要求设计一个时间复杂度为 O(log (m+n)) 的算法。常规做法就是先合并两个数组，然后排序取中位数即可，但是这样的时间复杂度是O(nlog (m+n))。 O(log (m+n)) 很明显是二分的思路，如果可以想到对k进行二分的话题目就变简单了，可惜第一次思考的时候局限在对数组进行二分。在考虑到对k进行二分之后，还需要注意很多的边界条件。

题目：

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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
示例 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

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<vector>
#include<string>
using namespace std;
double kth(vector<int>& nums1, int left1, int right1, vector<int>& nums2,int left2, int right2, int k){
    if(right1-left1 > right2-left2){ //将size小的数组放在前面，便于判断数组为空
        return kth(nums2,left2,right2,nums1, left1,right1,k);
    }
    if(left1>right1) //判断数组为空
        return nums2[left2+k-1]; //要加left偏移
    if(k==1){
        return min(nums1[left1], nums2[left2]);
    }
    
    int mid1=min(k/2, static_cast<int>(nums1.size()))-1, mid2=min(k/2,static_cast<int>(nums2.size()))-1;
    int res;
    if(nums1[left1+mid1]<nums2[left2+mid2]){  //要加left偏移
        res=kth(nums1, left1+mid1+1,right1,nums2,left2,right2,k-(mid1+1));
    }else
    {
        res=kth(nums1, left1,right1,nums2,left2+mid2+1,right2,k-(mid2+1));
    }
    return res;
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {    
    int len = nums1.size() + nums2.size();
    if(len%2==0)
        return (kth(nums1, 0, nums1.size()-1,nums2,0,nums2.size()-1,len/2) + kth(nums1, 0, nums1.size()-1,nums2,0,nums2.size()-1,len/2+1))/(double)2;
    else
        return kth(nums1, 0, nums1.size()-1,nums2,0,nums2.size()-1,(len+1)/2);
}

int main(){
    vector<int> nums1={1};
    vector<int> nums2={2,3,4,5,6};
    cout<<findMedianSortedArrays(nums1, nums2)<<endl;
    return 0;
}

参考 https://zhuanlan.zhihu.com/p/142548675