[leetcode]4. 寻找两个有序数组的中位数

题目描述：

难度：困难

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

• 示例 1:
  nums1 = [1, 3]
  nums2 = [2]
  则中位数是 2.0
• 示例 2:
  nums1 = [1, 2]
  nums2 = [3, 4]
  则中位数是 (2 + 3)/2 = 2.5

解题思路：

此题虽然定义难度为“困难”，但可能因为我对选择排序算法比较熟悉，并没有觉得这题有多难。很快就反应出解题思路：先定义两个变量i和j分别指向数组nums1和nums2的头部，分别移动i、j来遍历两个数组，谁对应的元素比较小就移动谁，这样移动下来的顺序就是两个数组合并在一起的排序。对于有序的合并数组，如果合并数组长度为奇数，则中间的数字就是中位数，对应的全局索引为(m+n)/2；如果合并数组的长度为偶数，则中间的两个数字就是中位数，对应的全局索引为(m+n)/2和(m+n)/2-1，对这两个数字求平均即可得最终结果。

该题目比较值得注意的一点是：对于异常处理的考虑，也就是nums1为空或者nums2为空的情况，以及各自只有一个元素的情况。最后，当各自只有一个元素时，是num1[0]>=nums2[0]还是相反。这些情况都测试没问题了，才能算是没问题。

另一种思路是采用二分查找和递归的方式来做，不断的排除掉不可能的数字，剩下的就是最终结果，这种思路回头有空再来补齐。

笨方法：

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