时间复杂度为$O(log(N+M))$。
class Solution {
public:
//k表示要找第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);
if (k == 1)
{
if (nums1.size() == i) return nums2[j]; //第一个数组为空就返回第二个数组的第一个元素
else return min(nums1[i], nums2[j]);
}
//若第一个数组已经为空,则直接返回第二个数组的中位数
if (nums1.size() == i) return nums2[j + k - 1];
int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
if (nums1[si - 1] > nums2[sj - 1])
return find(nums1, i, nums2, sj, k - (sj - j));
else
return find(nums1, si, nums2, j, k - (si - i));
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size() + nums2.size();
if (total % 2 == 0) //中位数有两个的情况
{
int left = find(nums1, 0, nums2, 0, total / 2);
int right = find(nums1, 0, nums2, 0, total / 2 + 1);
return (left + right) / 2.0;
}
else
return find(nums1, 0, nums2, 0, total / 2 + 1);
}
};