大致题意
就是求两个已排序的数组重新排序后的中位数
解题思路
这题题目规定是时间复杂度是O(log(m+n))，根据这个时间复杂度那么就是二分查找了
最开始没有看到时间复杂度搓了一个O(m+n)，还觉得LeetCode的hard难度一般般(((
事实证明我太蠢了
功力不够最后还是在网上找了解答
参考了这篇博客
这篇博客的解法是
-
首先，中位数，当数组长度是K位奇数时，那么中位数为该数组第K/2+1大的数
为偶数时，为第K/2大的数和第K/2+1大的数的和的一半，这个问题就变成了求两个升序序列重新排序后组成新的序列的第K的数
-
一个序列中，第k大的数字，去掉前面任意的m个数字，就变成了第k-m大的数字（废话）
-
最最最重要的一个就是
两个序列求合并之后的序列的第k大数字，那么第一个序列a第k/2大的数字如果小于第二个序列b第k/2大的数字，那么第一个序列a第k/2大的数字一定小于第k个数字（理由感性认知一下？）
同理得b，且如果两个相等的话，那么a第k/2大的数字就是整个数组第k大的数字
-
由上两条可以得得到
-
剩下的就是一些边界考虑问题了
-
本来都是用c++写的但是介于vector用不来还是用c指针比较爽
int findKnumber(int a[], int m, int b[], int n,int k) {
if (m > n) //使a数组都是更短的那个数组
findKnumber(b, n, a, m, k);
else {
if (m == 0) //当a数组为空时，第k小的数组就是b[k-1]
return b[k - 1];
if (k == 1) //当k为1时,就是比a数组和b数组首元素更小值
return min(a[0],b[0]);
int pa = min(m,k/2), pb = k - pa;
if (a[pa - 1] < b[pb - 1])
return findKnumber(a + pa, m - pa, b, n, k - pa);
else if (a[pa - 1] > b[pb - 1])
return findKnumber(a, m, b + pb, n - pb, k - pb);
else
return a[pa - 1];
}
return;
}
