Joey LIU | NANTSOU


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * As the time complexity is constrained to be O(log (m+n)), binary search is applied to finding out the medians.
 * No matter m + n is odd or even, the median of 2 arrays can be determined by the average of values at (m + n + 1)/2 
 * and (m + n + 2)/2. And binary search mentioned above is applied to (m + n + 1)/2 and (m + n + 2)/2 in each array.
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int l = (m + n + 1)/2, r = (m + n + 2)/2;
        return (findKth(nums1, 0, nums2, 0, l) + findKth(nums1, 0, nums2, 0, r))/2.0;
    }
    
    private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) {
            return nums2[j + k - 1];
        }
        if (j >= nums2.length) {
            return nums1[i + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }

        int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
        if (i + k/2 - 1 < nums1.length) {
            m1 = nums1[i + k/2 - 1];
        }
        if (j + k/2 - 1 < nums2.length) {
            m2 = nums2[j + k/2 - 1];
        }
        if (m1 < m2) {
            return findKth(nums1, i + k/2, nums2, j, k - k/2);
        } else {
            return findKth(nums1, i, nums2, j + k/2, k - k/2);
        }
    }
}