Leetcode初學——尋找兩個有序數組的中位數

題目：

因為這道題要求時間複雜度為O（log(m+n)），并且是讓我們求中位數

是以可以初步判斷題目中需要涉及到二分查找（如果不了解二分查找的可以自行搜尋，本文不做累述）

做一張簡單的原理圖：

數組1的長度 n1=4                                              數組2的長度 n2=6

是以k=（4+6）/2=5；

我們對這兩個數組，分别取一半，比較左半邊最大的兩個數的大小，舍去小的那一半

對剩下的數組繼續切割比較，繼續舍去3

是以可以找到第5個數 “4”，而n1+n2=10

是以中位數就是（4+5）/2=4.5；

将其轉換為代碼：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (n1>n2)
            return findMedianSortedArrays(nums2, nums1);
        int k = (n1 + n2 + 1)/2;
        int left = 0;
        int right = n1;
        while(left < right){
            int m1 = left +(right - left)/2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2-1])
                left = m1 + 1;
            else
                right = m1;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1-1],
                         m2 <= 0 ? Integer.MIN_VALUE : nums2[m2-1]);
        if ((n1 + n2) % 2 == 1)
            return c1;
        int c2 = Math.min( m1 >= n1 ? Integer.MAX_VALUE :nums1[m1],
                         m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
        
    }
}

作者：powcai
連結：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

 由于代碼我是看着powcai大佬寫的，是以這裡直接貼上大佬的代碼

大佬的代碼非常簡潔，最後的兩段更是精髓，統一對很多特殊情況做了處理,如：

{},{1}

{1,2},{3,4}

{2},{-2,-1};

········

令人佩服不已