Median Of Two Sorted Arrays

Oct 14, 2017

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2]

The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

• 整体长度是奇数，那么中位数是序列中的数
• 整体长度是偶数，那么中位数是序列中两个数的平均值。

double getKth(vector<int> &nums1,int beg1,int size1,vector<int> &nums2,int beg2,int size2,int k) {
//cout << beg1<<" " <<size1<<"\t"<<beg2<<" "<<size2<<"\t"<<k<<endl;
if (size1 > size2) {
return getKth(nums2,beg2,size2,nums1,beg1,size1,k);
}

if (size1 == 0) { return nums2[beg2 + k-1];}
if (k == 1) return min(nums1[beg1],nums2[beg2]);

int i = min(size1,k/2);
int j = min(size2,k/2);

if (nums1[beg1 + i-1] > nums2[beg2 + j-1]) {
return getKth(nums1,beg1,size1,nums2,beg2+j,size2-j,k-j);
} else
return getKth(nums1,beg1+i,size1-i,nums2,beg2,size2,k-i);
}


double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int l = (nums1.size() + nums2.size() + 1) >> 1;
int r = (nums1.size() + nums2.size() + 2) >> 1;
//cout << "#" << l << r << endl;
double dl = getKth(nums1,0,nums1.size(),nums2,0,nums2.size(),l);
double dr = getKth(nums1,0,nums1.size(),nums2,0,nums2.size(),r);
//cout << dl <<dr << endl;
return (dr+dl)/2;
}


LeetCodeLeetCode

Group-Anagrams

Permutations