LeetCode Median of Two Sorted Arrays两数列的中间数(二)
};
也可以用查找一般第K大的数的程序完成这道题，也是可以通过的：
[cpp]
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
vector vab(A, A+m);
for (int i = 0; i < n; i++)
{
vab.push_back(B[i]);
}
int k = (m+n)/2;
float fk = float(m+n)/2.0;
float fk2 = float(k);
double d1;
if(fk != fk2)
{
d1 = selectKthNumRand(vab, 0, vab.size()-1, k+1);
return d1;
}
int k1 = k+1;
d1 = selectKthNumRand(vab, 0, vab.size()-1, k1);
double d2 = selectKthNumRand(vab, 0, vab.size()-1, k);
return double(d1+d2) / 2.0;
}
int selectKthNumRand(vector &vi, int low, int up, int k)
{
int mIndex;
//注意这里会有几率是up=0， low=0，所以要作特殊处理
if(up-low != 0)
mIndex = rand()%(up-low) + low;
else mIndex = 0;
int mNum = vi[mIndex];
vector vec1, vec2, vec3;
for (int i = low; i <= up; i++)
{
if(vi[i] > mNum) vec3.push_back(vi[i]);
if(vi[i] == mNum) vec2.push_back(vi[i]);
if(vi[i] < mNum) vec1.push_back(vi[i]);
}
if(vec1.size()>=k)
return selectKthNumRand(vec1, 0, vec1.size()-1, k);
else if(vec1.size()+vec2.size()>=k)
return mNum;
else if(vec1.size()+vec2.size()
return selectKthNumRand(vec3, 0, vec3.size()-1, k-vec1.size()-vec2.size());
}