首页 > 代码库 > 【Leetcode】Median of Two Sorted Array II
【Leetcode】Median of Two Sorted Array II
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)).
非常经典的一个问题，如果直接查找中位数，即偶数约定向下取整，奇数就是严格的中位数，这个题目直接可以比较每个数组的mid来计算得到。
但是这个问题的需求更改为如果为偶数，则中位数为向下取整和向上取整两个数组的平均数，所以题目转换为两个有序数组的findKth的实现~
1st （18 tries）
class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { if(m > n) return findMedianSortedArrays(B,n,A,m); if((m+n)%2 == 0) return (findkth(A,m,B,n,(m+n)/2) + findkth(A,m,B,n,(m+n)/2+1))/2; else return findkth(A,m,B,n,(m+n)/2+1); } double findkth(int A[],int m,int B[],int n,int k) { if(m <= 0) return B[k-1]; if(n <= 0) return A[k-1]; if(k <= 1) return min(A[0],B[0]); int qa = min(m,k/2); int qb = k - qa; if(A[qa - 1] < B[qb - 1]) { return findkth(A+qa,m-qa,B,n,k-qa); } else if(A[qa - 1] > B[qb - 1]) { return findkth(A,m,B+qb,n-qb,k-qb); } else return A[qa - 1]; }};
2nd （5 tries）
class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { //奇数 if( (m + n) % 2 ) { return findk(A,m,B,n,(m + n)/2 + 1); } //偶数 else { return ( findk(A,m,B,n,(m + n)/2) + findk(A,m,B,n,(m + n)/2 + 1) ) / 2; } } //find two sorted array k num~ double findk(int A[],int m,int B[],int n,int k) { return findk(A,0,m-1,B,0,n-1,k); } double findk(int A[],int astart,int aend,int B[],int bstart,int bend,int k) { //step 1 if( astart > aend ) { return B[bstart + k - 1]; } if( bstart > bend) { return A[astart + k - 1]; } //step 2 //step 3 int amid = astart + (aend - astart)/2; int bmid = bstart + (bend - bstart)/2; int halflen = amid - astart + 1 + bmid - bstart + 1; if( A[amid] < B[bmid] ) { if( halflen > k ) { return findk(A,astart,aend,B,bstart,bmid - 1,k); } else { return findk(A,amid + 1,aend,B,bstart,bend,k - (amid - astart + 1) ); } } else { if( halflen > k ) { return findk(A,astart,amid - 1,B,bstart,bend,k); } else { return findk(A,astart,aend,B,bmid + 1,bend,k - (bmid - bstart + 1) ); } } }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。