- double findMedianSortedArrays(int A[], int m, int B[], int n)
- {
- if(m<0 || n<0) return 0;
- bool flag((m+n)%2==1? false:true);
- if(m==0 || n==0)
- {
- if(m==0) return findinonearray(B, 0, n-1, flag);
- else return findinonearray(A, 0, m-1, flag);
- }
- if(m==1 || n==1)
- {
- if(m==1)
- {
- int med=(n-1)/2;
- if(flag)
- {
- int temp;
- if(B[med]>=A[0])
- {
- if(med>0) temp=A[0]>B[med-1]? A[0]:B[med-1];
- else temp=A[0];
- }
- else
- {
- if(med+1<n) temp=A[0]>B[med+1]? B[med+1]:A[0];
- else temp=A[0];
- }
- return double(temp+B[med])/2;
- }
- else
- {
- if(B[med]>A[0]) return B[med];
- else return B[med+1]>A[0]? A[0]:B[med+1];
- }
- }
- else
- {
- int med=(m-1)/2;
- if(flag)
- {
- int temp;
- if(A[med]>=B[0])
- {
- if(med>0) temp=B[0]>A[med-1]? B[0]:A[med-1];
- else temp=B[0];
- }
- else
- {
- if(med+1<m) temp=B[0]>A[med+1]? A[med+1]:B[0];
- else temp=B[0];
- }
- return double(temp+A[med])/2;
- }
- else
- {
- if(A[med]>B[0]) return A[med];
- else return A[med+1]>B[0]? B[0]:A[med+1];
- }
- }
- }
- return findMedianSortedArrays(A, 0, m-1, m, B, 0, n-1, n, flag);
- }
- double findMedianSortedArrays(int A[], int abegin, int aend, int m, int B[], int bbegin, int bend, int n, bool flag)
- {
- if(abegin==aend && bbegin==bend) return double(A[abegin]+B[bbegin])/2;
- if(aend-abegin==1 || bend-bbegin==1)
- {
- if(aend-abegin==1) return findwithsurearray(A, abegin, aend, B, bbegin, bend, flag);
- else return findwithsurearray(B, bbegin, bend, A, abegin, aend, flag);
- }
- int amed=(abegin+aend)/2, bmed=(bbegin+bend)/2;
- if(getmed(A, abegin, aend)-getmed(B, bbegin, bend)<=0.0001 && getmed(A, abegin, aend)-getmed(B, bbegin, bend)>=-0.0001)
- {
- // if(flag)
- // {
- // if(amed+bmed+2>(m+n)/2) return A[amed];
- // else return double(A[amed]+(A[amed+1]>B[bmed+1]? B[bmed+1]:A[amed+1]))/2;
- // }
- // else return A[amed];
- return getmed(A, abegin, aend);
- }
- if(getmed(A, abegin, aend)>getmed(B, bbegin, bend))
- {
- if(getmed(A, abegin, aend)!=A[amed]) amed=amed+1;
- int step=(aend-amed)>(bmed-bbegin)? (bmed-bbegin):(aend-amed);
- return findMedianSortedArrays(A, abegin, aend-step, m, B, bbegin+step, bend, n, flag);
- }
- else
- {
- if(getmed(B, bbegin, bend)!=B[bmed]) bmed=bmed+1;
- int step=(bend-bmed)>(amed-abegin)? (amed-abegin):(bend-bmed);
- return findMedianSortedArrays(A, abegin+step, aend, m, B, bbegin, bend-step, n, flag);
- }
- return 0;
- }
- double findwithsurearray(int A[], int ab, int ae, int B[], int begin, int end, bool flag)
- {
- if(flag)//(end-begin)%2==1)//B shuangshu
- {
- int med=(begin+end)/2;
- if(A[ab]<=B[med] && A[ae]>=B[med+1]) return double(B[med]+B[med+1])/2;
- if(A[ab]>=B[med] && A[ae]<=B[med+1]) return double(A[ab]+A[ae])/2;
- if(A[ab]<=B[med] && A[ae]<=B[med+1] && A[ae]>=B[med]) return double(B[med]+A[ae])/2;
- if(A[ab]>=B[med] && A[ae]>=B[med+1] && A[ab]<=B[med+1]) return double(A[ab]+B[med+1])/2;
- if(A[ae]<=B[med])
- {
- int temp;
- if(med>begin) temp=A[ae]>B[med-1]? A[ae]:B[med-1];
- else temp=A[ae];
- return double(temp+B[med])/2;
- }
- if(A[ab]>=B[med+1])
- {
- med=med+1;
- int temp;
- if(med+1<=end) temp=A[ab]>B[med+1]? B[med+1]:A[ab];
- else temp=A[ab];
- return double(temp+B[med])/2;
- }
- }
- else//B danshu
- {
- int med=(begin+end)/2;
- if(B[med]>A[ae] || B[med]<A[ab])
- {
- if(B[med]>A[ae])
- {
- if(med>0) return A[ae]>B[med-1]? A[ae]:B[med-1];
- else return A[ae];
- }
- else
- {
- if(med<end) return A[ab]>B[med+1]? B[med+1]:A[ab];
- else return A[ab];
- }
- }
- else return B[med];
- }
- }
- double findinonearray(int A[], int begin, int end, bool flag)
- {
- if(begin>end) return 0;
- int med=(begin+end)/2;
- if(flag) return double(A[med]+A[med+1])/2;
- else return A[med];
- }
- double getmed(int A[], int begin, int end)
- {
- if((end-begin)%2==1) return double(A[(begin+end)/2]+A[(begin+end)/2+1])/2;
- else return A[(begin+end)/2];
- }
- //该片段来自于http://www.codesnippet.cn/detail/2005201512615.html
来源: http://www.codesnippet.cn/detail/2005201512615.html