首页 > 代码库 > [leetcode]Median of Two Sorted Arrays
[leetcode]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)).
看到sorted、log(m+n)肯定是二分查找了，只不过如何在两个排序数组中查找中间值呢？
算法思路：
这是某大神写的求两数组中第k小的数值的通用求法。大家可以参考一下，既然能求出任何k_th，那么中间值就不在话下了。本题假设是递增序列
假设a,b两个数组的长度都 > k/2，则取a[k/2 - 1]和b[k/2 - 1]做比较；
如果a[k/2 - 1]==b[k/2 - 1] ；则，返回a[k/2 - 1]。
如果a[k/2 - 1] > b[k/2 - 1] ；则b[k/2 - 1]之前的元素肯定是a,b两数组中k_th之前的元素了，之间剔除掉
同理a[k/2 - 1] < b[k/2 - 1] ； 将a[k/2 - 1]之前的元素剔除掉。
代码如下：
1 public class Solution { 2 public double findMedianSortedArrays(int a[], int b[]) { 3 if(a.length + b.length == 0) return 0; 4 int totalLength = a.length + b.length; 5 if((totalLength & 1 )== 1){ 6 return findK_thElement(a, b, totalLength / 2 + 1); 7 }else{ 8 return (findK_thElement(a, b, totalLength / 2) + findK_thElement(a, b, totalLength / 2 + 1)) / 2.0; 9 }10 }11 12 private double findK_thElement(int[] a,int[] b,int k){13 if(a.length > b.length) return findK_thElement(b, a, k);14 if(a.length == 0) return b[k - 1];15 if(k == 1) return Math.min(a[0], b[0]);16 int aIndex = Math.min(a.length, k / 2);17 int bIndex = k - aIndex;18 if(a[aIndex - 1] == b[bIndex - 1]){19 return a[aIndex - 1];20 }else if(a[aIndex - 1] < b[bIndex - 1]){21 return findK_thElement(Arrays.copyOfRange(a, aIndex, a.length), b, k - aIndex);22 }else{23 return findK_thElement(a, Arrays.copyOfRange(b, bIndex, b.length), k - bIndex);24 }25 }26 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。