LeetCode_4_MedianofTwoSortedArrays

題目分析：

題目要求找中位數(shù)淑玫，如果我們可以構(gòu)造一個(gè)函數(shù)荒叶，
使用二分查找的方式查找兩數(shù)組合并后任意位置上的數(shù)，題目可解喻奥。

解法一：

//log(m + n) -- best
//寫(xiě)一個(gè)兩個(gè)有序數(shù)組中找第k個(gè)數(shù)的函數(shù) -- k從1開(kāi)始
public static double findMedianSortedArrays3(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    if (1 == (1 & total))//奇數(shù)
        return findKth(nums1, 0, nums2, 0, total / 2 + 1);
    else
        return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
}

/**
 * 核心思路:每次排除min(nums1.length - a, k / 2)個(gè)結(jié)果 -- 盡量 k / 2
 */
public static int findKth(int[] nums1, int a, int[] nums2, int b, int k) {//k從1開(kāi)始
    if (nums1.length - a > nums2.length - b)//確保num2更長(zhǎng)
        return findKth(nums2, b, nums1, a, k);
    if (0 == nums1.length - a)//有一個(gè)數(shù)組被排除完了 -- 未必是一開(kāi)始傳入的第一個(gè)
        return nums2[b + k - 1];
    if (1 == k)//必要的邊界條件
        return Math.min(nums1[a], nums2[b]);
    /**
     * 每次排除掉 k1或k2個(gè)數(shù) k也相應(yīng)迭代
     */
    int k1 = Math.min(nums1.length - a, k / 2);
    int k2 = k - k1;
    if (nums1[a + k1 - 1] < nums2[b + k2 - 1])
        return findKth(nums1, a + k1, nums2, b, k - k1);//排除左邊
    else if (nums1[a + k1 - 1] > nums2[b + k2 - 1])
        return findKth(nums1, a, nums2, b + k2, k - k2);//排除右邊
    else
        return nums1[a + k1 - 1];//巧妙的剪枝
}

解法二：

/**
 *  根據(jù)中位數(shù)定義分別在兩個(gè)數(shù)組進(jìn)行分割
 *  保證兩點(diǎn):
 *  1. mid1 + mid2 == (m - mid1) + (n - mid2) ==> mid1 = (m + n) / 2 - mid2
 *  2. max(m[i - 1], n[j - 1]) <= min(m[i], n[j])
 *
 *  切出來(lái)不滿(mǎn)足條件 再根據(jù)情況二分調(diào)整 mid1和mid2聯(lián)動(dòng) 只需要保證left或者right正確二分調(diào)整即可
 *
 *  核心思路總結(jié):構(gòu)造出滿(mǎn)足條件的兩個(gè)分割點(diǎn)僵朗，然后二分移動(dòng)其中一個(gè)，
 *  并根據(jù)相應(yīng)規(guī)則調(diào)整另一個(gè)屑彻，二分的左右方向選取問(wèn)題得到了解決Ｑ槊怼！社牲！
 */
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    if (m < n) return findMedianSortedArrays(nums2, nums1);//確保數(shù)組1長(zhǎng)度大于數(shù)組2 -- m >= n
    if (0 == n) return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;//如果數(shù)組2是空 -- 剪枝
    int left = 0, right = 2 * n;//n是較短數(shù)組的長(zhǎng)度
    while (left <= right) {
        int mid2 = (left + right) / 2;//右邊部分切割位置
        int mid1 = m + n - mid2;//左邊部分切割位置
        //四種極限切割情況 以及默認(rèn)正常情況
        //為了L R比較大小時(shí)候統(tǒng)一 有一些小操作 仔細(xì)觀察即可
        double leftMax1 = 0 == mid1 ? Double.MIN_VALUE : nums1[(mid1 - 1) / 2];
        double leftMax2 = 0 == mid2 ? Double.MIN_VALUE : nums2[(mid2 - 1) / 2];
        double rightMin1 = mid1 == m * 2 ? Double.MAX_VALUE : nums1[mid1 / 2];
        double rightMin2 = mid2 == n * 2 ? Double.MAX_VALUE : nums2[mid2 / 2];
        if (leftMax1 > rightMin2) left = mid2 + 1;
        else if (leftMax2 > rightMin1) right = mid2 - 1;
        else return (Math.max(leftMax1, leftMax2) + Math.min(rightMin1, rightMin2)) / 2;
    }
    return -1;
}