输入：int nums1[1,3,5,8] int nums2[2,9,10,11]
过程：求两个排序的数组的中位数
输出：6.5
注意：数组排序方式一致，都是升序或者都是降序
算法：
- 求中位数说白了就是求特殊的第k大或者第k、k+1大的数。但是这里比较棘手的是要在两个数组中求
- 题目时间复杂度有要求log(m+n)，基本确定使用二分查找，难点就在于怎么在两个数组中实现二分查找。
思路：
基本知道求两数组中位数有以下两种情况：
- 当m+n为偶数，中位数=(数组[(m+n)/2]+数组[(m+n)/2+1])/2.0
- 当m+n奇数时，中位数=数组[(m+n)/2]
由上可知，假设m+n=k，要求的就是两个数组的第k/2大值或者第k/2+1大值，所以需要设置一个函数来求第k大值。如果数组1为空，第k大值就在数组2中，反过也是一样。如果k=1说明求的是最小值，只需返回判断数组1[0]和数组2[0]中的较小值即可。
过一遍算法：假设数组1 arr1 = [1,3,5,8] 数组 arr2 = [2,9,10,11]，这里我们知道k=4 or 5(因为合并后的长度为偶数)
先求第4大，
比较arr1[m/2]和arr2[n/2]，明显arr1[m/2]小于arr2[n/2]，所以我们知道arr[0]arr[m/2]都小于arr2[n/2]；所以下一步就需要把目标定在arr1[m/2+1]arr[m-1]；
我们查找的范围缩小到arr1[m/2+1]arr[m/2+m/2]和arr2[0]arr[n/2]；知道查找的范围缩小为1，就找到我们要找的第4大的值为5，
同理可求出第5大的值为8，平均值就是要求的中位数6.5
查找第k大函数如下：
int findKth(vector<int>& nums1, int m, vector<int>& nums2, int n, int k)
{
if (m >= nums1.size()) return nums2[n + k - 1];
if (n >= nums2.size()) return nums1[m + k - 1];
if (k == 1) return min(nums1[m], nums2[n]);
int p1 = m + k / 2 - 1;
int p2 = n + k / 2 - 1;
int mid1 = p1 < nums1.size() ? nums1[p1] : INT_MAX;
int mid2 = p2 < nums2.size() ? nums2[p2] : INT_MAX;
if (mid1 < mid2)
{
return findKth(nums1, m + k / 2, nums2, n, k - k/2);
}
else
{
return findKth(nums1, m, nums2, n + k/2, k- k/2);
}
}
求中位数代码如下：
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if (len % 2 == 0) {
return (findKth(nums1, 0, nums2, 0, len / 2) + findKth(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
}
return findKth(nums1, 0, nums2, 0, (len + 1) / 2);
}
