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)
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
相关阅读更多精彩内容
- 问题描述 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...