**
Question:

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)).

**

My code:

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null)
            return 0;
        if (nums1.length == 0 && nums2.length == 0)
            return 0;
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0)
            if (n % 2 == 1)
                return nums2[n / 2];
            else
                return ((double)nums2[n / 2] + (double)nums2[n / 2 - 1]) / 2.0;
        else if (n == 0)
            if (m % 2 == 1)
                return nums1[m / 2];
            else
                return ((double)nums1[m / 2] + (double)nums1[m / 2 - 1]) / 2.0;
        
        
        int indexOfNums1 = 0;
        int indexOfNums2 = 0;
        boolean isOutOfRange = false;
        int[] mergeArray = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            
            if (indexOfNums1 < m && (nums1[indexOfNums1] < nums2[indexOfNums2] || isOutOfRange)) {
                mergeArray[i] = nums1[indexOfNums1];
                indexOfNums1++;
            }
            else {
                mergeArray[i] = nums2[indexOfNums2];
                if (indexOfNums2 < n - 1)
                    indexOfNums2++;
                else
                    isOutOfRange = true;
            }
        }
        
        if ((m + n) % 2 == 1)
            return mergeArray[(m + n) / 2];
        else
            return ((double)mergeArray[(m + n) / 2] + (double)mergeArray[(m + n) / 2 - 1]) / 2.0;
        
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] a = {100001};
        int[] b = {100000};
        System.out.println(test.findMedianSortedArrays(a, b));
    }
}

My test result:

Paste_Image.png

這次的難度是hard，但是我一看到就有了思路，然后花了十分鐘寫了出來。
這不就是歸并排序（Merge Sort）的簡單版本么。。。
給兩個已排序好的數(shù)列，然后將它們合并，獲得一個新的數(shù)列
來，復(fù)習(xí)下歸并排序。
我自己創(chuàng)造的一個圖書。
. . . . . . . . 一個array，用歸并排序來處理
. . . . | . . . . 分成兩個array，分別進(jìn)行歸并排序
. . | . . | . . | . . 對于每個子array,再次分成兩個array，分別進(jìn)行歸并排序。
此時每個部分只有兩個數(shù)字了， lo指向第一個，頭。hi指向最后一個，也是第二個，尾。
于是進(jìn)行簡單的排序。完成了。退回到上步。
. . | . . | . . | . . 此時的子array都是已經(jīng)排序好了的。于是將 1,2子array歸并，3,4子array歸并。
. . . . | . . . . 此時的兩個子array也是已經(jīng)排序好了的。于是將它們歸并，得到最后的排序結(jié)果。
. . . . . . . .

然后歸并排序的核心就是這次作業(yè)寫的。
兩個array，然后我先創(chuàng)建一個array長度是他們的長度和。
然后通過移動指針，將兩個數(shù)組對應(yīng)位置較小的拷貝進(jìn)入mergeArray，然后指針再往前一格。這樣，掃描(m + n)次就能完成了。
然后處理一些數(shù)組越界問題。就差不多。復(fù)雜度是 N * Log(N)

**
總結(jié)：
歸并排序。
數(shù)組越界。
**

最近兩次作業(yè)都是十幾分鐘寫出來了。。。是我太強(qiáng)了嗎？
我不覺得。我覺得是評測系統(tǒng)有問題。這兩道題目正常人應(yīng)該都半小時內(nèi)就能做出來吧。
最近聽了荔枝FM的一個廣播。額，首先聲明，我絕對不是做廣告的人。
很感動。然后那么一句話。
**
其實(shí)我也是一個普通人啊。
**
打到我內(nèi)心了。
小說世界里， 泰廣，米可，最后能破鏡重圓。
現(xiàn)實(shí)世界里，會有這般失而復(fù)得的事嗎？
所以，確定你想要的，然后堅(jiān)持下去。
讀者們肯定看不懂我說的這些話，但你呢，應(yīng)該看得懂吧。
我愿意為你改變很多，放棄很多。
你也愿意為我忍耐很多，擔(dān)心很多。
異地異國實(shí)在是太難熬，但熬出頭了呢。
如果因?yàn)槟敲匆患氖?，咱們最終放棄。不知道你會怎么想。
我的話，一定會有新的女朋友，家庭。
但這份對你的遺憾，會陪伴我，直到進(jìn)入棺材。

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return -1;
        }
        else if (nums2.length < nums1.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        else if (nums2.length == 0) {
            return -1;
        }
        
        
        int m = nums1.length;
        int n = nums2.length;
        
        int half = (m + n + 1) / 2;
        int imin = 0;
        int imax = m;
        while (imin <= imax) {
            int i = (imax + imin) / 2;
            int j = half - i;
            if (i - 1 >= 0 && j < n && nums1[i - 1] > nums2[j]) {
                imax = i - 1;
            }
            else if (j - 1 >= 0 && i < m && nums2[j - 1] > nums1[i]) {
                imin = i + 1;
            }
            else {
                int left = 0;
                if (i == 0) {
                    left = nums2[j - 1];
                }
                else if (j == 0) {
                    left = nums1[i - 1];
                }
                else {
                    left = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                
                if ((m + n) % 2 == 1) {
                    return left;
                }
                
                int right = 0;
                if (i == m) {
                    right = nums2[j];
                }
                else if (j == n) {
                    right = nums1[i];
                }
                else {
                    right = Math.min(nums1[i], nums2[j]);
                }
                
                return (left + right) / 2.0;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums1 = new int[]{1,2};
        int[] nums2 = new int[]{3,4,5,6};
        double ret = test.findMedianSortedArrays(nums1, nums2);
        System.out.println(ret);
    }
}

reference：
https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation/2

這道題目實(shí)在是太惡心了。弄了一個多小時。
corner case 太多了。。。

看下講解，思路清晰了很多。但是還是調(diào)了很久很久。
最大的問題是，得把短的作為切割的第一數(shù)組，即， i

因?yàn)槿绻虚L的，作為i
那么 j很有可能變成負(fù)數(shù)，會出現(xiàn)錯誤。
如果切短的，就不會用這個問題。

還有個注意的地方就是：
half = (m + n + 1) / 2;
這樣保證，如果 m + n 是偶數(shù)，
那么左右部分個數(shù)相等。
如果是奇數(shù)，那么左邊會多一個。

而且imax = m 而不是 m - 1，真的求中點(diǎn)。
如果m是奇數(shù)，就是正中點(diǎn)。如果m是偶數(shù)，是中間兩個數(shù)右邊那個。
這些正好都是我們需要的特性。

實(shí)在是太惡心了。

加油！

Anyway, Good luck, Richardo! -- 09/01/2016