Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int N1 = nums1.size(), N2 = nums2.size();
int total = N1 + N2;
int left = (total+1)/2;
int right = (total + 2) / 2;
//If the final array is odd, the median will calculate twice
return (getKth(nums1, 0, N1, nums2, 0, N2, left) + getKth(nums1, 0, N1, nums2, 0, N2, right))/2.0;
}
double getKth(vector<int> &nums1, int start1, int end1, vector<int> &nums2, int start2, int end2, int k)
{
int len1 = end1 - start1, len2 = end2 - start2;
if(len1>len2)
return getKth(nums2, start2, end2, nums1, start1, end1, k);
if(len1 == 0)
return nums2[k + start2 -1];
if(k == 1) return min(nums1[start1], nums2[start2]);
int index1 = start1 + min(len1, k/2) - 1;
int index2 = start2 + min(len2, k/2) - 1;
if(nums1[index1]>nums2[index2])
return getKth(nums1, start1,end1,nums2, index2+1, end2, k - (index2 - start2 + 1));
else
return getKth(nums1, index1+1, end1, nums2, start2, end2, k - (index1 - start1 + 1));
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment