首页 > 代码库 > Median of Two Sorted Arrays
Median of Two Sorted Arrays
There are two sorted arrays A and B 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)).
思路：转化为两个有序列第K大的值。
1 class Solution { 2 public: 3 double findMedianSortedArrays( int A[], int m, int B[], int n ) { 4 int a1 = FindKthNum( (m+n-1)/2, A, m, B, n ); 5 int a2 = FindKthNum( (m+n)/2, A, m, B, n ); 6 return ( a1 + a2 ) / 2.0; 7 } 8 private: 9 int FindKthNum( int k, const int* A, int m, const int* B, int n ) {10 if( m == 0 ) { return B[k]; }11 if( n == 0 ) { return A[k]; }12 if( k == 0 ) { return A[0] < B[0] ? A[0] : B[0]; }13 int k1 = -1, k2 = -1;14 if( m < n ) {15 k1 = min( k/2, m-1 ), k2 = k - k1 - 1;16 } else {17 k2 = min( k/2, n-1 ), k1 = k - k2 - 1;18 }19 if( A[k1] < B[k2] ) {20 return FindKthNum( k2, &A[k1+1], m-k1-1, &B[0], k2+1 );21 } else if( A[k1] > B[k2] ) {22 return FindKthNum( k1, &A[0], k1+1, &B[k2+1], n-k2-1 );23 }24 return B[k2];25 }26 };
Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。