public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
int k = m + n;
//如果是奇数 那么找到中间元素
if ((k & 1) > 0){
return findKth(A,0, m, B,0, n, k / 2 + 1);
}else{
//如果是偶数 找中间两个数的平均数
return (findKth(A,0, m, B,0, n, k / 2) + findKth(A,0, m, B,0, n, k / 2 + 1)) / 2;
}
}
/**
* 从两个数组中找到第k大数
* @param A
* @param pluseNuma A数组开始遍历的基准位置
* @param m
* @param B
* @param pluseNumb
* @param n
* @param k
* @return
*/
public double findKth(int A[],int pluseNuma, int m, int B[],int pluseNumb, int n, int k){
//算法的计算基础是m <= n
//m is equal or smaller than n
if (m > n)
return findKth(B,pluseNumb, n, A,pluseNuma, m, k);
//如果长度为0 那么就从b中找到结果
if (m == 0)
return B[pluseNumb+k-1];
//如果找到两个数组中的第k个元素为第1个或者0个元素 那么去两个元素的最小值就可以了
if (k <= 1)
return min(A[pluseNuma], B[pluseNumb]);
//看A数组里面的数据还够不够k的一半
int pa = min(k/2, m);
int pb = k - pa;
//A中小于B中的情况
if (A[pluseNuma+pa-1] < B[pluseNumb+pb-1]){
//A中元素减少
return findKth(A,pluseNuma+pa, m - pa, B,pluseNumb, n, k - pa);
}
else if(A[pluseNuma+pa-1] > B[pluseNumb+pb-1]){
//b中元素范围减少
return findKth(A, pluseNuma,m, B,pluseNumb+pb, n - pb, k - pb);
//正好相等的情况
}else
return A[pluseNuma+pa-1];
}
public int min(int a,int b){
if(a < b) return a;
return b;
}
Median of Two Sorted Arrays(Java)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 问题描述 There are two sorted arrays nums1 and nums2 of size ...
- There are two sorted arrays nums1 and nums2 of size m and...
- There are two sorted arrays nums1 and nums2 of size m and...
