1、题目：
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
2、法1：归并排序
nums1的最后一个数和nums2的最后一个数对比。如果nums1的值大，将该值存入新的结果数组中，并将nums1最后一个数删除，则nums1的倒数第二个数就成为了最后一个。这样只要一直将nums1和nums2最后一个数对比。
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ nums1.reverse() nums2.reverse() temp=[] while nums1 and nums2: if nums1[-1]<=nums2[-1]: temp.append(nums1[-1]) nums1.pop() else: temp.append(nums2[-1]) nums2.pop() if not nums1 and nums2: nums2.reverse() temp.extend(nums2) elif not nums2 and nums1: nums1.reverse() temp.extend(nums1) if len(temp)%2==1: return temp[len(temp)//2] else: return (temp[len(temp)//2]+temp[len(temp)//2-1])/2
法2：分治法：
分：由于两个数组合并之后的中位数，比较nums1和nums2的中位数a,b，若a<b，则合并数组的中位数在a的右边，b的左边。若a>b，则合并数组的中位数在a的左边，b的右边。
假设：
nums1中位数 i=len(A)//2
nums2中位数 j=k-i 【k=(len(A)+len(B))//2】
治：最小的子问题有三种：
一、nums1空，nums2只有一个值【返回nums2的值，因为合并的中位数也是该值】
二、nums1只有一个值，nums2空【返回nums1的值，因为合并的中位数也是该值】
三、nums1和nums2都只有一个值a和b【此时应该返回两个值a,b。继续分nums1和nums2，发现一种情况分为空和非空的可以返回一个值，另一种情况出现无法索引到数组中1的值。】
如nums1=【1】，nums2=【2】
m=len(nums1)+len(nums2)=2，则应返回k=m//2-1=0和k=m//2=1的值。
当k=0时，i=len(nums1)/2=0, j=k-i=0, 【i,j作为两个数组的中位数索引】 nums1[i]=1, nums[j]=2,比较两者大小，1<2，取1右边的数（包括1）为【1】，取2左边的数（不包括2）为空【】，则【1】和【】返回1。----------------这种情况只会返回nums1和nums2中较小的数。
当k=1时，i=len(nums1)/2=0，j=k-i=1，发现没有这个索引，所以这种情况发生时无法返回数。这是需要强制给它返回一个值，即返回nums1和nums2中较大的值。
故第三种情况：if k==1 and len(nums1)==1 and len(nums2)==1:
return max(nums1[0],nums[0])
def findMid(nums1,nums2): l=len(nums1)+len(nums2) return findKthMid(nums1,nums2,l//2) if l%2==1 else (findKthMid(nums1,nums2,l//2-1)+findKthMid(nums1,nums2,l//2))/2def findKthMid(nums1,nums2,k): if not nums1 and nums2: return nums2[k] if not nums2 and nums1: return nums1[k] if k==1 and len(nums1)==1 and len(nums2)==1: return max(nums1[0],nums2[0]) i=len(nums1)//2 j=k-i if nums1[i]>nums2[j]: return findKthMid(nums1[:i],nums2[j:],i) else: return findKthMid(nums1[i:],nums2[:j],j)