4. Median of Two Sorted Arrays

题目：

here 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)).
You may assume nums1 and nums2 cannot be both empty.

Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
题意： 给出两个已经排序好的数组，找出两个数组的中位数，要求时间复杂度为O（log(m+n)）。
思路： 此问题最为简单的办法就是将两个数组归并为一个，然后找出归并后的数组的中位数，如下代码1实现，但是归并数组时间复杂度为O（m+n）不符合题意，虽然最终测试结果也能通过。
　　　此题既然被定义为hard难度，自然是有它的原因的，要求使时间复杂度为Ｏ（log(m+n))，第一反应就是使用二分法，对于一个数组使用二分法的确可以在log的时间复杂度里找到特定的数，但是这是两个数组，且不能合并（合并的时间复杂度为O（m+n）），该怎么做呢？我们先考虑找到第K大的数，我们需要将K进行二分，划分为两部分，假定第一部分为i = k/2， 第二部分j = k-i， 然后比较第一个数组第i个数与第二个数组第j个数的大小，抛弃小的那一部分，因为小的那一部分一定在第K大数之前，然后大的那个数组保持不变，小的那个数组保留抛弃后的部分，那么此时寻找第K大的数变成了寻找第K减去抛弃部分长度的数，如抛弃的是第一个数组前i个数，那么K= K-i，再次迭代，二分K值，直到最终k=1，比较两个数组第一位数的大小，返回较小的值即可。考虑特殊情况：如果某一个数组全部被抛弃，则表明该数组里所有的数都在第K大的数之前，此时返回第二个数组第K（若干次迭代后的K值）个数的值。
　　　此题寻找的是中位数的值，此时要分奇偶来讨论，若两个数组长度和为奇数，则中位数为最中间的那个数，若两数组长度和为偶数，则中位数为最中间两位数的平均值。我们可以令K1 = （m+n+1）/2， K2 = （m+n+2)/2，若K1和K2相等，则K=K1=K2，若不等，则分别找出第K1和第K2的数去平均值即为最终中位数的结果。
　　　
代码1：（归并排序）

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n1 = len(nums1)
        n2 = len(nums2)
        merge_num = []
        i = 0
        j = 0
        while(i <= n1-1 and j <= n2-1):
            if nums1[i] < nums2[j]:
                merge_num.append(nums1[i])
                i += 1
            else:
                merge_num.append(nums2[j])
                j += 1
                
        merge_num.extend(nums1[i:])
        merge_num.extend(nums2[j:])
        if len(merge_num) % 2 == 0:
            mid = len(merge_num) //2
            return (merge_num[mid] + merge_num[mid-1]) / 2.0
        else:
            return merge_num[len(merge_num)// 2]

代码2：二分法

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n = len(nums1)
        m = len(nums2)
        k1 = (m+n+1)//2
        k2 = (m+n+2)//2
        # print(k1, k2)
        if k1 == k2:
            return self.find_k(k1, nums1, nums2)
        else:
            num1 = self.find_k(k1, nums1, nums2)
            # print(num1)
            num2 = self.find_k(k2, nums1, nums2)
            # print(num2)
            return (num1 + num2)/2.0

    def find_k(self, k, nums1, nums2):
        if len(nums1) == 0:
            return nums2[k-1]
        elif len(nums2) == 0:
            return nums1[k-1]
        if k == 1:
            return min(nums1[0], nums2[0])
        mid_k = k // 2
        if mid_k > len(nums1):
            i = (len(nums1)+1)//2
            j = k - i
        elif k - mid_k > len(nums2):
            j = (len(nums2)+1) // 2
            i = k - j
        else:
            i = mid_k
            j = k - mid_k
        if nums1[i-1] < nums2[j-1]:
            nums1 = nums1[i:]
            k = j
            num = self.find_k(k, nums1, nums2)
        else:
            nums2 = nums2[j:]
            k = i
            num = self.find_k(k, nums1, nums2)
        return num