思路
原问题难以直接递归求解，所以我们先考虑这样一个问题：
在两个有序数组中，长度分别为n、m, 找出第k小数。
如果该问题可以解决，那么第 k = (n+m)/2 小数就是我们要求的中位数.
先从简单情况入手，假设 m,n ≥ k/2，我们先从 nums1 和 nums2 中各取前 k/2 个元素：
- 如果 nums1[k/2−1] > nums2[k/2−1]，则说明 nums2 中的前 k/2 个元素一定都小于等于第 k 小数，所以我们可以先刨去这些数，将问题归约成在剩下的数中找第 k−⌊k/2⌋ 小数.
- 如果 nums1[k/2−1] ≤ nums2[k/2−1]]，可说明 nums1 中的前 k/2 个元素一定都小于等于第 k 小数，同样可将问题的规模减少一半.
现在考虑边界情况，如果m<k/2，则我们从 nums1 中取m个元素，从nums2 中取 k/2 个元素（由于 k=(n+m)/2，因此 m,n 不可能同时小于 k/2.）：
-
如果 nums1[m−1]>nums2[k/2−1]，则 nums2 中的前 k/2 个元素一定都小于等于第 k 小数，我们可以将问题归约成在剩下的数中找第 k−⌊k/2⌋ 小数.
-
如果 nums1[m−1]≤nums2[k/2−1]，则 nums1 中的所有元素一定都小于等于第 k 小数，因此第k小数是 nums2[k−m−1].
时间复杂度分析：k=(m+n)/2，且每次递归 k 的规模都减少一半，因此时间复杂度是 O(log(m+n)).
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total % 2 == 0){
int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
return (left + right) / 2.0;
}else{
return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
}
}
int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k){
//令num1总是较短的那一个
if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
//如果nums1走到了头,那nums2[j+k-1]就是中位数
if (nums1.size() == i) return nums2[j + k - 1];
//如果走到了答案所在位置,返回nums1[i]和nums[j]中相对小的那一个
if (k == 1) return min(nums1[i], nums2[j]);
//找到nums1和nums2分别的中点，需要注意的是num1的长度可能小于k/2，所以i+k/2可能越界，需要取min值
int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
if (nums1[si - 1] > nums2[sj - 1])
return findKthNumber(nums1, i, nums2, sj, k - k / 2);
else
return findKthNumber(nums1, si, nums2, j, k - (si - i));
}
};
Q1、if (nums1[si - 1] > nums2[sj - 1])
寻找第k个最小的数，给出的是从1开始的下标，但是实际数组下标从0开始，因此需要减1
比如： 1 2 3 4 5 6
第3小的数是3，下标是2