Median of Two Sorted Arrays(Java

2016-11-22  本文已影响18人  Persistence2
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;
    }
上一篇 下一篇

猜你喜欢

热点阅读