1 题目
题目：两个排序数组的中位数（Median of two Sorted Arrays）
描述：两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
中位数的定义：
- 这里的中位数等同于数学定义里的中位数。
- 中位数是排序后数组的中间值。
- 如果有数组中有n个数且n是奇数，则中位数为A[(n - 1) / 2]A[(n?1)/2]。
- 如果有数组中有n个数且n是偶数，则中位数为 (A[(n - 1) / 2] + A[(n - 1) / 2 + 1]) / 2。
- 比如：数组A=[1,2,3]的中位数是2，数组A=[1,19]的中位数是10。
lintcode题号——65，难度——hard
样例1：
输入：
A = [1,2,3,4,5,6]
B = [2,3,4,5]
输出：3.50
解释：合并后的数组为[1,2,2,3,3,4,4,5,5,6]，中位数为(3 + 4) / 2。
样例2：
输入：
A = [1,2,3]
B = [4,5]
输出：3.00
解释：合并后的数组为[1,2,3,4,5]，中位数为3。
2 解决方案
2.1 思路
??取两个排序数组的中位数，看起来没有难度，可以合并两个数组再取，但是题中要求在O(log(m+n))的时间复杂度下完成，就有些复杂了，因为要达到log这个数量级，所以考虑通过二分的思想来解决，两个数组并不是同一个整体，二分思想要求每次将问题的规模缩小，直到能够直接解决。
??将取中位数的问题转变为取两个数组中从小到大的第k = (m+n)/2个数，此时我们想抛掉一些不可能是结果的数，对比a数组中的第k/2个数（假设为keyA）和b数组中的第k/2个数（假设为keyB），找出较小的数（假设keyA<keyB），此时我们研究a数组的前k/2个数与b数组的前k/2个数，一共k个数，分析keyA可能处在这k个排好序的数的什么位置，keyA能排序到的最远位置就是第k-1位，此时前面的位置由a数组的前k/2 - 1个数与b数组的前k/2 - 1个数填满，以此为前提，因为keyA以及a数组中keyA之前的数都不可能是第k个数，所以我们可以抛掉a数组中keyA和keyA之前的所有数，再在新的a数组和b数组中寻找第k - k/2个数，以此类推即可。
2.2 图解
数组a、b：
a[a1,a2,……,am] 长度m
b[b1,b2,……,bn] 长度n
寻找中位数，即第k=(m+n)/2个数，取a中的第k/2个数与b中的第k/2个数比较：
a[a1,a2,…,a(k/2),……,am] 长度m
b[b1,b2,…,b(k/2),……,bn] 长度n
若a(k/2) < b(k/2),此时分析a数组的前k/2个数与b数组的前k/2个数进行排序的情况是：
a1,a2,b1,a3,a4,a5,b2,…,a(k/2),…,a(k/2 + 2),b(k/2-1),b(k/2)
|<- A中前k/2 - 1个数 ->|
|<- B中前k/2 - 1个数 ->|
考虑A(k/2)能够排到的最远位置，即将能够放在A(k/2)前的数都放在它前面：
a1,a2,b1,a3,a4,a5,b2,…,a(k/2 - 1),b(k/2-1),a(k/2),…,a(k/2 + 2),…,b(k/2)
|<- A中前k/2 - 1个数 ->|
|<- B中前k/2 - 1个数 ->|
此时A(k/2)的位置是第k-1位，即A(k/2)永远不可能排到第k位。
抛掉A中前k/2个数，形成新的数组a、b：
a[a(k/2 + 1),……,am]
b[b1,b2,…,b(k/2),……,bn]
寻找中位数，即第k - k/2个数，依次类推即可找到答案。
2.3 时间复杂度
??时间复杂度为O(log(m+n))。
2.4 空间复杂度
??空间复杂度为O(1)。
3 源码
细节：
- 当两个数组长度和为基数的时候，直接找中间序号的数为中位数即可；当长度和为偶数的时候，找出两个最靠近中间的数，取平均值即可。
- 递归的出口有两个，当其中一个数组为空时，返回不空数组的第k个值；当k=1时，返回两个数组中较小的首元素。
- 如果k/2序号超出数组的长度，则返回INT_MAX，目的是抛掉另一个数组的前k/2个数。
C++版本：
/**
* @param a: An integer array
* @param b: An integer array
* @return: a double whose format is *.5 or *.0
*/
double findMedianSortedArrays(vector<int> &a, vector<int> &b) {
// write your code here
int length = (int)a.size() + (int)b.size();
int mid = length / 2;
if (length % 2 != 0)
{
// 总长度为奇数，中位数为中间数的值
return findTheKth(a, 0, b, 0, mid + 1);
}
else
{
// 总长度为偶数，中位数为中间两数的平均值
return (double)(findTheKth(a, 0, b, 0, mid) + findTheKth(a, 0, b, 0, mid + 1)) / 2;
}
}
int findTheKth(vector<int> &a, int startA, vector<int> &b, int startB, int k)
{
// 递归的出口
if (startA > (int)a.size() - 1) // 数组a已经抛完
{
return b.at(startB + k - 1); // 直接返回b中第k个数
}
if (startB > (int)b.size() - 1) // 数组b已经抛完
{
return a.at(startA + k - 1); // 直接返回a中第k个数
}
// 递归的出口
if (k == 1)
{
return a.at(startA) < b.at(startB) ? a.at(startA) : b.at(startB); // 返回两个数组中较小的第一个数
}
int n = k / 2;
int kthValueInA = (startA + n > (int)a.size()) ? INT_MAX : a.at(startA + n - 1); // 获取A中第n个值，越界则赋值MAX
int kthValueInB = (startB + n > (int)b.size()) ? INT_MAX : b.at(startB + n - 1); // 获取B中第n个值，越界这赋值MAX
if (kthValueInA < kthValueInB) // 抛掉A中前 k/2 个元素
{
return findTheKth(a, startA + n, b, startB, k - n);
}
else // 抛掉B中前 k/2 个元素
{
return findTheKth(a, startA, b, startB + n, k - n);
}
}
