median of two sorted arrays的时间复杂度(附上了过了oj的代码）# JobHunting - 待字闺中
x*0
1 楼
关于这道题的时间复杂度，有个疑问。
基本算法是参考
ref1:
http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electri
和
ref2:
http://leetcode.com/2011/03/median-of-two-sorted-arrays.html#co
来做的。
大致介绍一下ref1中所描述的算法，基本思路是binary search.
假设数组A和B，长度分别为nA和nB。nA+nB=n。
（1）median 不是在A中就是在B中。（基本是一句废话，:-))
（2）选择数组A的median,假设其index为i=（l+r)/2（初始时l=0，r=nA-1）。比较A[i
]和B[j]，B[j+1]，j=n/2 - i - 1。j做如此选择，是因为如果A[i]是meidian of two
sorted arrays的话，A[i]必须大于B中的j个元素。
（3）如果B[j]<=A[i]<=B[j+1],那么A[i]必定是我们要找的结果。
（4）如果A[i]arrays
（5）如果A[i]>B[j+1],那么所有大于A[i]的元素肯定不成。
（6）当发现median不在数组A中时（l>r），切换到B中去寻找，重复(2)-(4)。
根据我的理解，这个算法的复杂度应该为：log（nA)+log(nB)才对。但是ref1中说是
log（n）。
大家怎么看的呀。
附上过了oj的代码：格式不太好。
下面的链接给出了很好的代码显示：
http://discuss.leetcode.com/questions/142/median-of-two-sorted-
class Solution {
public:
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-1, (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 B[j+1]) return findMedian(A, B, l, i-1,nA,
nB);
else {
if ( (nA+nB)%2 == 1 ) return A[i];
if (i>0) {
int pre = (j < 0) ? A[i - 1] : max(B[j], A[i-1]);
return (A[i]+pre)/2.0;
}
return (A[i]+B[j])/2.0;
}
}
double findMedianSortedArrays(int A[], int n, int B[], int m) {
return findMedian(A, B, max(0, (m+n)/2-m), min(n-1, (m+n)/2), n, m);
}
};
基本算法是参考
ref1:
http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electri
和
ref2:
http://leetcode.com/2011/03/median-of-two-sorted-arrays.html#co
来做的。
大致介绍一下ref1中所描述的算法，基本思路是binary search.
假设数组A和B，长度分别为nA和nB。nA+nB=n。
（1）median 不是在A中就是在B中。（基本是一句废话，:-))
（2）选择数组A的median,假设其index为i=（l+r)/2（初始时l=0，r=nA-1）。比较A[i
]和B[j]，B[j+1]，j=n/2 - i - 1。j做如此选择，是因为如果A[i]是meidian of two
sorted arrays的话，A[i]必须大于B中的j个元素。
（3）如果B[j]<=A[i]<=B[j+1],那么A[i]必定是我们要找的结果。
（4）如果A[i]arrays
（5）如果A[i]>B[j+1],那么所有大于A[i]的元素肯定不成。
（6）当发现median不在数组A中时（l>r），切换到B中去寻找，重复(2)-(4)。
根据我的理解，这个算法的复杂度应该为：log（nA)+log(nB)才对。但是ref1中说是
log（n）。
大家怎么看的呀。
附上过了oj的代码：格式不太好。
下面的链接给出了很好的代码显示：
http://discuss.leetcode.com/questions/142/median-of-two-sorted-
class Solution {
public:
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-1, (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);
else {
if ( (nA+nB)%2 == 1 ) return A[i];
if (i>0) {
int pre = (j < 0) ? A[i - 1] : max(B[j], A[i-1]);
return (A[i]+pre)/2.0;
}
return (A[i]+B[j])/2.0;
}
}
double findMedianSortedArrays(int A[], int n, int B[], int m) {
return findMedian(A, B, max(0, (m+n)/2-m), min(n-1, (m+n)/2), n, m);
}
};
