題目描述：
難度：困難
給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)刹淌，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))葱蝗。
你可以假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空忍些。
- 示例 1:
nums1 = [1, 3]
nums2 = [2]
則中位數(shù)是 2.0 - 示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
則中位數(shù)是 (2 + 3)/2 = 2.5
解題思路：
此題雖然定義難度為“困難”觉吭，但可能因?yàn)槲覍?duì)選擇排序算法比較熟悉，并沒有覺得這題有多難憔古。很快就反應(yīng)出解題思路：先定義兩個(gè)變量i和j分別指向數(shù)組nums1和nums2的頭部遮怜，分別移動(dòng)i、j來(lái)遍歷兩個(gè)數(shù)組鸿市，誰(shuí)對(duì)應(yīng)的元素比較小就移動(dòng)誰(shuí)锯梁，這樣移動(dòng)下來(lái)的順序就是兩個(gè)數(shù)組合并在一起的排序。對(duì)于有序的合并數(shù)組焰情，如果合并數(shù)組長(zhǎng)度為奇數(shù)陌凳，則中間的數(shù)字就是中位數(shù)，對(duì)應(yīng)的全局索引為(m+n)/2烙样；如果合并數(shù)組的長(zhǎng)度為偶數(shù)冯遂，則中間的兩個(gè)數(shù)字就是中位數(shù)，對(duì)應(yīng)的全局索引為(m+n)/2和(m+n)/2-1谒获，對(duì)這兩個(gè)數(shù)字求平均即可得最終結(jié)果蛤肌。
該題目比較值得注意的一點(diǎn)是：對(duì)于異常處理的考慮，也就是nums1為空或者nums2為空的情況批狱，以及各自只有一個(gè)元素的情況裸准。最后，當(dāng)各自只有一個(gè)元素時(shí)赔硫，是num1[0]>=nums2[0]還是相反炒俱。這些情況都測(cè)試沒問(wèn)題了，才能算是沒問(wèn)題爪膊。
另一種思路是采用二分查找和遞歸的方式來(lái)做权悟，不斷的排除掉不可能的數(shù)字，剩下的就是最終結(jié)果推盛，這種思路回頭有空再來(lái)補(bǔ)齊峦阁。
笨方法：
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m,n=len(nums1),len(nums2)
i,j,cnt,ans=0,0,0,0 #nums1,nums2的索引
while i<m or j<n:
pre_ans=ans
if j>=n or (i<m and j<n and nums1[i]<=nums2[j]):
ans=nums1[i]
i+=1
else:
ans=nums2[j]
j+=1
if (m+n)%2==1:
if cnt==int((m+n)/2):
return ans*1.0
else:
if cnt==int((m+n)/2):
return (ans+pre_ans)*1.0/2
cnt+=1
return 0
