β

Median of Two Sorted Arrays

Michael's Blog 45 阅读

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).

Example 1:

nums1 = [1, 3]  
nums2 = [2]
The median is 2.0  

Example 2:

nums1 = [1, 2]  
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5  
public class Solution {  
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return -1;
        }
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 != 0) {
            return (double)findKth(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1);
        } else {
            return (findKth(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1) 
                   + findKth(nums1, nums2, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
        }
    }
    int findKth(int[] A, int[] B, int k, int aStart, int aEnd, int bStart, int bEnd) {
        int aLen = aEnd - aStart + 1;
        int bLen = bEnd - bStart + 1;
        if (aLen == 0) {
            return B[bStart + k];
        }
        if (bLen == 0) {
            return A[aStart + k];
        }
        if (k == 0) {
            return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
        }
        int aMid = aLen * k / (aLen + bLen);
        int bMid = k - aMid - 1;
        aMid = aStart + aMid;
        bMid = bStart + bMid;
        if (A[aMid] > B[bMid]) {
            k = k - (bMid - bStart + 1);
            aEnd = aMid;
            bStart = bMid + 1;
        } else {
            k = k - (aMid - aStart + 1);
            bEnd = bMid;
            aStart = aMid + 1;
        }
        return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
    }
}
作者:Michael's Blog
Thoughts, stories and ideas.
原文地址:Median of Two Sorted Arrays, 感谢原作者分享。

发表评论