描述：

給定兩個有序的陣列，nums1, nums2 , 找出這兩個陣列中所有數字的中位數。

例如：

解法1：

這是最容易的想到的方法，直接將兩個陣列拼接，然後重新排序，並找出中間的數。

但該解法需要將兩個陣列的所有元素重新排序，並沒有考慮題目中兩個原陣列都是有序的條件，執行速度依賴於排序演算法，在快排的情況下為 O((m+n)log(m+n)) 。m,n 分別為兩個陣列的長度。

解法2：

感謝 @小藍 提供的第二種解法，利用了兩個陣列有序的初始狀態，不斷比較將較小的值 push 進新陣列，並且在新陣列長度達到原陣列的一半的時候找到中位數。

該方法只需要迴圈原來兩個陣列長度之和的一半，縮短了執行時間，達到了 O(m+n)

解法3：

要取一個數組的中位數，需要滿足兩個條件:

中位數左右的數字數量相等中位數左邊的所有數字都比它小，右邊的所有數字都比它大

因此，我們只需要將原來兩個陣列中的所有數字平均分成兩堆，並且保證左邊一堆的最大值 lMax <= 右邊一堆的最小值 rMin，那麼就保證了左邊所有的數 >= 右邊所有的數。那麼 lMax 以及 rMin 就是這所有數中間的數字：

m+n 為偶數的情況，中位數為 (lMax+rMin) /2m+n 為奇數的情況，假設右邊的數字比左邊多一個，那麼，中位數為 rMin

程式碼如下：

該演算法最壞情況下只需要遍歷兩個陣列中較短的一個數組，使運算時間縮短為 O(n), n為較短的陣列的長度。