Problem
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
Understanding
Median, 在統(tǒng)計學(xué)中叫做中位數(shù)贫橙，能夠?qū)⒁粋€數(shù)列分成不包含其自身的兩個部分御吞，兩個部分長度相等。如果是處理一個有序數(shù)組蛀序，則如果數(shù)組長度為奇數(shù)纤控，則取中間位挂捻，如果為偶數(shù)則取中間兩數(shù)的均值。
測試用例
[1,3]
[2,3]
2.5
[1,10]
[2,3]
2.5
解法
歸并排序通過合并兩個有序的數(shù)列得到一個新有序數(shù)列船万，這就是解法的思想刻撒。然后取中間的一位或者兩位的均值。
不過耿导，與歸并排序的不同的是声怔，并不需要實(shí)際的合并，只需要找到最后數(shù)組的中間一位或者兩位數(shù)即可舱呻。使用兩個變量last,cur來記錄即可醋火。
空間復(fù)雜度O(1), 時間復(fù)雜度O(m+n)
代碼(C++)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int length=nums1.size()+nums2.size();
const int indexEnd=(length%2==0)?(length+1)/2:length/2;
int i1=0,i2=0;
int index=0;
int cur,last;
while(i1 < nums1.size() && i2<nums2.size() && index <=indexEnd )
{
index++;
last=cur;
if(nums1[i1]>nums2[i2])
cur=nums2[i2++];
else
cur=nums1[i1++];
}
while(i1 < nums1.size() && index <=indexEnd)
{
last=cur;
cur=nums1[i1++];
index++;
}
while(i2 < nums2.size() && index <= indexEnd)
{
last=cur;
cur=nums2[i2++];
index++;
}
return length%2==0?(last+cur)/2.0:cur;
}
};
