贡献一个Median of two sorted arrays的java code

发信人: Bao0007 (宝哥), 信区: JobHunting
标  题: 贡献一个Median of two sorted arrays的java code
关键字: leetcode,java
发信站: BBS 未名空间站 (Wed Jun 26 11:42:13 2013, 美东)

通过了leetcode 的大小OJ. 基于findKth, 好处是只有三个简单的special cases。没
有以前一个大牛的C++解法简洁，但也不是特别的麻烦。

code如下：
//-------------------------------------------------------------------
public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;

        if( (m + n) % 2 != 0 ) // odd number of total elements
            return (double)findKth(A, B, (m + n) / 2, 0, m-1, 0, n-1);
        else { // even
            return ( findKth(A, B, (m + n) / 2, 0, m-1, 0, n-1) +
                findKth(A, B, (m + n) / 2 - 1, 0, m-1, 0, n-1) ) * 0.5;
        }
    }

    public static int findKth(int A[], int B[], int k,
            int ista_A, int iend_A, int ista_B, int iend_B) {

        int nA = iend_A - ista_A + 1;
        int nB = iend_B - ista_B + 1;

        // Special cases
        if( nA == 0 ) return B[ista_B + k];
        if( nB == 0 ) return A[ista_A + k];
        if( k == 0) return A[ista_A] < B[ista_B] ? A[ista_A] : B[ista_B];

        // Reduce search ranges in A and B
        int imid_A = nA * k / (nA + nB);
        int imid_B = k - imid_A - 1;

        // Add offset so that imid_A and imid_B index directly into A and B,
        // respectively
        imid_A += ista_A;
        imid_B += ista_B;


        if( A[imid_A] > B[imid_B] ) {
            k -= imid_B - ista_B + 1;
            iend_A = imid_A;
            ista_B = imid_B + 1;
        } else {
            k -= imid_A - ista_A + 1;
            iend_B = imid_B;
            ista_A = imid_A + 1;
        }
       
        return findKth(A, B, k, ista_A, iend_A, ista_B, iend_B);

    }
}




--

※ 修改:·Bao0007 於 Jun 26 11:57:59 2013 修改本文·[FROM: 128.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 128.]

http://www.mitbbs.com/article_t/JobHunting/32467775.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大