题目描述
LeetCode原题链接：4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
题干分析
中位数的概念大家应该不陌生，对于一个数组，如果数组中元素个数是奇数，则中位数就是最中间的那一个数；如果是偶数，则是中间两个数的平均值。对于题目中的 nums1 和 nums2，合并后数组的长度是 m+n，我们需要分奇偶情况来分别计算其中位数。
不过这样感觉稍微有点麻烦，我们可以稍微改造一下奇数的情况，让它和偶数时的计算方式一样，也是求两个数的平均值，这样我们就不用分情况讨论了。怎么改造呢？假设数组长度是L，我们可以去寻找数组中的第 (L+1)/2 个和第 (L+2)/2 个元素，这两个数的平均值就是要求的中位数。举个??，对于奇数个元素数组[1, 2, 3]，第 (L+1)/2 个和第 (L+2)/2 个元素都指向2，二者相加除以二得到的还是2；对于偶数个元素数组[1, 2, 3, 4]，第 (L+1)/2=2 个和第 (L+2)/2=3 个元素分别是2和3，其平均数是2.5也就是数组饿中位数。nice！
二分法查找第 k 个元素
好了，接下来，题目就变成去找nums1和nums2按升序合并后的新数组中的第 (m+n+1)/2 个和第 (m+n+2)/2 个元素了，我们可以把这个过程抽象成一个函数，即在两个数组中去寻找合并后数组的第 k 个元素。那么如何在不使用新数组的前提下去寻找第 k 个元素呢？这就要用到二分法了，对，在两个数组中使用二分法，对 k 进行二分。我们试着倒推一下，现在我们有一个长度为 m+n 的空数组，需要我们从 nums1 和 nums2 中取值去填充这个空数组，直到我们填满前 k 个位置为止；换句话说，k就是我们需要填充进空数组中的元素的个数。接下来，我们去 nums1 和 nums2 中去找这些要填充的数字。为了加快查找速度，这里就要使用二分法了：分别在升序排列的 nums1 和 nums2 中去寻找第 k/2 个元素。令 nums1 中第 k/2 个元素是 value1，nums2 中第 k/2 个元素是 value2，我们去比较 value1 和 value2 的大小，小的那一个方的前 k/2 个数将被填充到空数组中，到此为止一轮搜索结束，我们缩小了需要填充的空位的个数，进入下一轮循环。注意，下一轮循环的时候上一轮已经被填充了数我们就可以直接舍掉不看了，从那个位置的下一个位置开始继续查找，同时，需要填充的元素个数也要相应的减去 k/2，变为 (k - k / 2)。
注意一些特殊情况：
- 当数组中有一个是空数组时，就可以直接降级为在另一个数组中用下标索引找第 k 个数了；
- 如果两个数组均不为空，且k=1，则可直接比较 nums[0] 和 nums[1] 的取较小值就可以了；
- 如果某个数组中的个数不足 k/2 个显然是无法确定是否取舍该数组中的数的，而又因为比较的是谁的值最小，于是这种情况下需要把 value 设为 INT_MAX 避免被淘汰。
再用个??来演示一下上面的过程加深印象：
已知nums1=[2, 4, 9, 10]，nums2=[1, 3, 8]，求合并后的数组中的第5个数。
第一轮搜寻我们发现 nums2[1] < nums1[1]，而 nums2 又是升序排列的，因此 nums2 前两位可以直接拿去填充空数组；对于 nums2，1和3就被淘汰了，可以理解为 nums2 数组在一轮循环后由[1, 3, 8]变成了[8]。
下面进入第二轮搜寻，nums1[0] < nums2[0]，用nums1的前一位数去填充空数组。这里可能有人会问用来填充空数组的元素是否需要按照升序排列？注意了，这里的空数组只是我们用来方便理解而造出来的，实际并没有这么一个数据结构存在（我们并不是真正合并 nums1 和 nums2 然后生成一个新的升序排列的合成数组），我们只需要找到所有数中较小的 k 个数就可以了，至于这些数内部是按什么顺序排列的我们并不关心（可以当作是 k 个较小数的集合）。进一步说，我们填充空数组不是目的，缩短两个原数组、淘汰较小的数才是目的。
实际编程时，这个过程可以用指针的移动来替代：分别对两个数组各设置一个指针指向每次搜寻时的起始位置，初始化时两个指针均指向数组下标为0的位置；每轮搜寻结束后，仅对被淘汰了较小数的那个数组，移动其指针到第 (k/2 + 1) 位置，然后进行下一轮搜索。
第三轮搜寻：
到第四轮搜寻时，k已经变成了1，我们只需比较 nums1[0] 和 nums2[0] 的大小取较小值就可以得到最终结果了！
搜寻结束，第5个数字是8！
代码示例（c++）
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 4 int m = nums1.size(), n = nums2.size(); 5 // 无论奇偶情况，都用两个数的平均值来表示中位数 6 int left = (m + n + 1) / 2, right = (m + n + 2) / 2; 7 return (findTargetIndex(nums1, nums2, left, 0, 0) + findTargetIndex(nums1, nums2, right, 0, 0)) / 2.0; 8 } 9 int findTargetIndex(vector<int>& nums1, vector<int>& nums2, int k, int start1, int start2) { 10 // 当起始位置超过数组下标范围时，说明该数组无效，降级为在另一个数组中直接用下标索引第k个数 11 if(start1 >= nums1.size()) return nums2[start2 + k - 1]; 12 if(start2 >= nums2.size()) return nums1[start1 + k - 1]; 13 // 当要寻找第一个数时，直接比较两个数组第一个数的大小，取小返回即可 14 if(k == 1) return min(nums1[start1], nums2[start2]); 15 // nums1中第 k/2 个数 16 int value1 = (start1 + k / 2 - 1 < nums1.size()) ? nums1[start1 + k / 2 - 1] : INT_MAX; 17 // nums2中第 k/2 个数 18 int value2 = (start2 + k / 2 -1 < nums2.size()) ? nums2[start2 + k / 2 -1] : INT_MAX; 19 // 比较value1和value2大小，决定缩短哪个数组（移动哪个数组的起始位置指针）进行下一轮搜寻 20 if(value1 <= value2) { 21 // 缩短nums1数组 22 return findTargetIndex(nums1, nums2, k - k / 2, start1 + k / 2, start2); 23 } 24 else { 25 // 缩短nums2数组 26 return findTargetIndex(nums1, nums2, k - k / 2, start1, start2 + k / 2); 27 } 28 } 29 };
参考：https://grandyang.com/leetcode/4/