class Solution {
public:
double FindKthNumber(vector<
int> numbers1, vector<
int>numbers2,
int len1,
int len2,
int start1,
int start2,
int k)
{
if (len1 >
len2)
return FindKthNumber(numbers2, numbers1, len2, len1, start2, start1, k);
if (len1 ==
0)
return numbers2[start2 + k -
1];
if (k ==
1)
return min(numbers1[start1], numbers2[start2]);
int p1 = min(k /
2, len1);
int p2 = k -
p1;
if (numbers1[start1 + p1 -
1] < numbers2[start2 + p2 -
1])
return FindKthNumber(numbers1, numbers2, len1 - p1, len2, start1 + p1, start2, k -
p1);
else if (numbers1[start1 + p1 -
1] > numbers2[start2 + p2 -
1])
return FindKthNumber(numbers1, numbers2, len1, len2 - p2, start1, start2 + p2, k -
p2);
else
return numbers1[start1 + p1 -
1];
}
double findMedianSortedArrays(vector<
int>& nums1, vector<
int>&
nums2)
{
int len1=
nums1.size();
int len2=
nums2.size();
int k=(len1+len2)/
2;
if((len1+len2)%
2==
0)
return (FindKthNumber(nums1,nums2,len1,len2,
0,
0,k)+FindKthNumber(nums1,nums2,len1,len2,
0,
0,k+
1))/
2;
else
return FindKthNumber(nums1,nums2,len1,len2,
0,
0,k+
1);
}
};
转载于:https://www.cnblogs.com/vincent93/p/7588887.html
