首页 > 代码库 > Median of Sorted Arrays
Median of 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)).
double findMedian(int A[], int B[], int l, int r, int nA, int nB){ if (l > r) return findMedian(B, A, max(0, (nA+nB)/2-nA), min(nB, (nA+nB)/2), nB, nA); int i = (l+r)/2; int j = (nA+nB)/2 - i - 1; if (j >= 0 && A[i] < B[j]) return findMedian(A, B, i+1, r, nA, nB); else if (j < nB-1 && A[i] > B[j+1]) return findMedian(A, B, l, i-1, nA, nB); else { if ((nA+nB)%2 == 1) return A[i]; else if (i > 0) return (A[i]+max(B[j], A[i-1]))/2.0; else return (A[i]+B[j])/2.0; }}
A O(m+n) solution:
bool findMedian(int A[], int B[], int nA, int nB){ assert(A && B && nA >= 0 && nB >= 0); bool odd = (nA + nB) % 2 == 1 ? true : false; int medianIndex = (nA+nB)/2; if (odd == false) medianIndex++; int i = 0; int j = 0; int count = 0; int pre = -1; int cur = -1; while (i < nA && j < nB) { count++; if (A[i] < B[j]) { if (count == medianIndex) { cur = A[i]; break; } pre = A[i]; i++; } else { if (count == medianIndex) { cur = B[i]; break; } pre = B[j]; j++; } } if (i == nA) { cur = B[j+medianIndex-count-1]; if (medianIndex-count > 1) pre = B[j+medianIndex-count-2]; } else if (j == nB) { cur = A[i+medianIndex-count-1]; if (medianIndex-count > 1) pre = A[i+medianIndex-count-2]; } if (odd == true) return cur; else return (cur+pre)/2.0;}
Median of Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。