Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
求兩個(gè)數(shù)組合并后的中位數(shù)
Algorithm：
中位數(shù)求法：把長(zhǎng)度為k數(shù)組從小到大排列，返回中間位置的元素。
k為奇數(shù)，中位數(shù)為nums[k/2]，k為偶數(shù)中位數(shù)為(nums[k/2]+nums[(k/2)⑴]/2
算法1：歸并兩個(gè)數(shù)組后，找中位數(shù)，復(fù)雜度O(m+n)
算法2：類似2分查找，不需要?dú)w并，復(fù)雜度O(log(m+n))
現(xiàn)在詳細(xì)說(shuō)明解法2，我們可以把問(wèn)題轉(zhuǎn)化為尋覓第k大的元素
假定AB的長(zhǎng)度都大于k/2，比較A[(k/2)⑴]和B[(k/2)⑴]，有3種情況
1、A[k/2⑴] = B[k/2⑴]
此時(shí)，我們就已找到第k大的元素，即element=A[k/2⑴]=B[k/2⑴]
2、A[k/2⑴] < B[k/2⑴]
此時(shí)，意味著A[0]~A[k/2⑴]都比第k個(gè)元素小，由于A[0]~A[k/2⑴]有k/2個(gè)元素，B[0]~B[k/2⑴]有k/2個(gè)元素，如果A[k/2⑴]是比第k個(gè)元素還大的元素，假定A[k/2⑴]是比第k+1小的元素，那末B[k/2⑴]最少是第k+2大的元素。但是在A中最多有k/2⑴個(gè)元素小于A[k/2⑴]，在B中最多有k/2⑴個(gè)元素小于A[k/2⑴]，總共最多有(k/2⑴+k/2⑴)即k⑵個(gè)元素。所以A[k/2⑴]不可能大于第k個(gè)元素。所以我們可以刪去，然后找第k-k/2=k/2個(gè)元素。
3、A[k/2⑴] > B[k/2⑴]
類似2
在這里要注意3種特殊情況
1、如果AB有1個(gè)是空，則返回非空數(shù)組下標(biāo)為k⑴的元素，即A[k⑴]或B[k⑴]
2、如果k==1，則返回min{A[0],B[0]}
3、如果k/2比短的數(shù)組長(zhǎng)的話（假定是A），則比較A[m⑴]和B[k/2⑴]
Ex:
A{1,3,7,8} m1=4
B{2,4,5,6,7,8,9,10,12} m2=9
由于刪除元素較為麻煩，所以在程序中設(shè)兩個(gè)變量begin1，begin2作為起始元素。再設(shè)置m1和m2作為有效數(shù)組長(zhǎng)度。
1、合并后的數(shù)組，長(zhǎng)度為m1+m2=13，那末我們要找出第13/2+1=7，即k=7，第7大的元素。剛開(kāi)始begin1和begin2都為0，m1=4，m2=9
2、A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[2]=5，所以我們刪去B中的2，4，5，在程序中，我們可使begin2指針指向元素6，即begin2=3，m2=9⑶=6，現(xiàn)在我們要找出k⑶即第4大的元素
3、k=4，begin1=0，begin2=3，m1=4，m2=6，A[begin1+k/2⑴]=A[1]=3 < B[begin2+k/2⑴]=B[7]，所以我們刪去A中1，3，begin1=0+2=2，m1=4⑵=2，現(xiàn)在我們要找出k⑵，即第2大的元素
4、k=2，begin1=2，begin2=3，m1=2，m2=6，A[begin1+k/2⑴]=A[2]=7 > B[begin2+k/2⑴]=B[3]=6，所以我們刪去B中6，begin2=3+1=4，m2=6⑴=5，現(xiàn)在我們要找出k⑴，即第1大的元素
5、k=1，begin1=2，begin2=4，m1=2，m2=5比較A[begin1]=A[2]=7,B[begin2]=B[4]=7，返回7，終究結(jié)果為7
Accepted Code：
算法1：
class Solution {
public:
vector<int> MergeSort(vector<int>& nums1, vector<int>& nums2)
{
vector<int> res;
int i=0,j=0;
while(i<nums1.size() && j<nums2.size())
{
if(nums1[i]<=nums2[j])
{
res.push_back(nums1[i]);
i++;
}
else
{
res.push_back(nums2[j]);
j++;
}
}
while(i<nums1.size())
{
res.push_back(nums1[i]);
i++;
}
while(j<nums2.size())
{
res.push_back(nums2[j]);
j++;
}
return res;
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> temp=MergeSort(nums1,nums2);
double res;
int len=temp.size();
if(temp.size()%2==0)
res=(double)(temp[len/2]+temp[(len/2)⑴])/2;
else
res=temp[len/2];
return res;
}
};
算法2：
class Solution {
public:
double find_kth(vector<int>& nums1,vector<int>& nums2,int m1,int m2,int k,int begin1,int begin2)
{
if(m1 > m2)
return find_kth(nums2,nums1,m2,m1,k,begin2,begin1);
if(m1 == 0)
return nums2[k⑴];
if(k == 1)
return nums1[begin1] < nums2[begin2]?nums1[begin1]:nums2[begin2];
int a=min(k/2,m1); //the ath element in A
int b=k-a; //the bth element in B
if(nums1[begin1+a⑴] < nums2[begin2+b⑴]) //compare the ath element in A and the bth element in B
return find_kth(nums1,nums2,m1-a,m2,k-a,begin1+a,begin2);
else
return find_kth(nums1,nums2,m1,m2-b,k-b,begin1,begin2+b);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m1=nums1.size();
int m2=nums2.size();
int k=(m1+m2)>>1;
if((m1+m2)%2==1)
return find_kth(nums1,nums2,m1,m2,k+1,0,0);
else
return (find_kth(nums1,nums2,m1,m2,k+1,0,0)+find_kth(nums1,nums2,m1,m2,k,0,0))/2;
}
};
