递归
将问题拆分为子问题:将两个有序数组排序,求第k个数。每次递归将k减半,原问题$k=(m+n)/2$.
$O(log(m+n))$
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int tot = nums1.size() + nums2.size();
if(tot % 2) {
return find(nums1, 0, nums2, 0, tot / 2 + 1);
}
else {
int left = find(nums1, 0, nums2, 0, tot / 2);
int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
return (left + right) / 2.0;
}
return 0.0;
}
// num1[i]开始的数组和nums[j]开始的数组一起排序后的第k个数是什么
int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
if(nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
// k=1 即求最小数
if(k == 1) {
// num1[i:]为空,选择nums[j:]中第k个数
if(nums1.size() == i) return nums2[j+k-1];
else return min(nums1[i], nums2[j]);
}
// nums1[i:]为空,从nums[j:]中选第k个数
if(nums1.size() == i) return nums2[j + k - 1];
// si为nums1[i:]第k/2个数的下一个位置.nums1更短,有可能越界; k可能是奇数
int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
if(nums1[si-1] < nums2[sj-1]) return find(nums1, si, nums2, j, k - (si - i));
else return find(nums1, i, nums2, sj, k - (sj - j));
}
};