[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]之前的元素剔除掉。

代码如下：

public class Solution {
public double findMedianSortedArrays(int a[], int b[]) {
        if(a.length + b.length == 0) return 0;
        int totalLength = a.length + b.length;
        if((totalLength & 1 )== 1){
            return findK_thElement(a, b, totalLength / 2 + 1);
        }else{
            return (findK_thElement(a, b, totalLength / 2) + findK_thElement(a, b, totalLength / 2 + 1)) / 2.0;
        }
    }
    
    private double findK_thElement(int[] a,int[] b,int k){
        if(a.length > b.length) return findK_thElement(b, a, k);
        if(a.length == 0) return b[k - 1];
        if(k == 1) return Math.min(a[0], b[0]);
        int aIndex = Math.min(a.length, k / 2);
        int bIndex = k - aIndex;
        if(a[aIndex - 1] == b[bIndex - 1]){
            return a[aIndex - 1];
        }else if(a[aIndex - 1] < b[bIndex - 1]){
            return findK_thElement(Arrays.copyOfRange(a, aIndex, a.length), b, k - aIndex);
        }else{
            return findK_thElement(a, Arrays.copyOfRange(b, bIndex, b.length), k - bIndex);
        }
    }
}