首页 > 代码库 > Median of Two Sorted Arrays
Median of Two 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)).
1 public class Solution { 2 public double findMedianSortedArrays(int A[], int B[]) { 3 int alen = A.length; 4 int blen = B.length; 5 if((alen + blen) % 2 == 1) return findKthElement(A, B, 0, alen - 1, 0, blen - 1, (alen + blen + 1) / 2); 6 else return (double) (findKthElement(A, B, 0, alen - 1, 0, blen - 1, (alen + blen) / 2) + findKthElement(A, B, 0, alen - 1, 0, blen - 1, (alen + blen + 2) / 2)) / 2.0; 7 } 8 private int findKthElement(int arra[], int arrb[], int ast, int and, int bst, int bnd, int num){ 9 if(ast > and) return arrb[bst + num - 1];10 if(bst > bnd) return arra[ast + num - 1];11 int amid = (ast + and) / 2;12 int bmid = (bst + bnd) / 2;13 int len = amid - ast + 1 + bmid - bst + 1;14 if(arra[amid] < arrb[bmid]){15 if(len <= num) return findKthElement(arra, arrb, amid + 1, and, bst, bnd, num - amid + ast - 1);16 else return findKthElement(arra, arrb, ast, and, bst, bmid - 1, num);17 }else{18 if(len <= num) return findKthElement(arra, arrb, ast, and, bmid + 1, bnd, num - bmid + bst - 1);19 else return findKthElement(arra, arrb, ast, amid - 1, bst, bnd, num);20 }21 }22 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。