4. Median of Two Sorted Arrays

两个顺序数组的中位数

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
根据已知的两个长度不一样的数组，寻找两个数组的中位数。
The overall run time complexity should be O(log (m+n)).
要求是：时间复杂度log(m+n)。我觉得这才是为什么被设置为hard类型的原因吧。

题目思考

一上来我就用list.extend 和 list.sort 进行排序。想想应该不会这么简单吧。以下是我的代码：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1.extend(nums2)
        nums1.sort()
        tmp = int(len(nums1)/2)
        if (len(nums1)-2*tmp)==0:
            return (nums1[tmp]+nums1[tmp-1])/2
        else:
            return nums1[tmp]

写完之后想看答案，才发现这题是没有答案的。
只能参考评论区了。
这里由于下标的原因，tmp的数值需要注意下，下标是从0开始，所以偶数个的时候的下标是tmp和tmp-1进行求中位数，基数位数的时候直接用tmp下标就行。我在刚开始的时候，忘记了下标，都用了+1显示，就不太对了。

评论区解析

这题，由于我用的是python，所以有取巧的成分。
没想到的是，评论区居然有和我类似的代码。
评论区的主流其实用的是 binary-search 二分查找法来做的。
习惯性的贴出别人大佬的代码。

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        
        if len(nums2) < len(nums1):
            return self.findMedianSortedArrays(nums2, nums1)
        
        n1, n2 = len(nums1), len(nums2)
        low, high = 0, n1
        
        while low <= high:
            cut1=(low + high) // 2
            cut2= (n1 + n2 + 1) // 2 - cut1
            
            l1= float(-inf) if cut1 == 0 else nums1[cut1-1]
            l2= float(-inf) if cut2 == 0 else nums2[cut2-1]
            r1= float(inf) if cut1 == n1 else nums1[cut1]
            r2= float(inf) if cut2 == n2 else nums2[cut2]
            
            if l1 <= r2 and l2 <= r1:
                if((n1+n2) % 2 == 0):
                    return (max(l1, l2) + min(r1, r2)) / 2
                else:
                    return max(l1, l2)
            elif l1 > r2:
                high = cut1 - 1
            else:
                low = cut1 + 1
        
        return 0.0

一开始我对这个算法还不是很理解。幸好有国外大神分享的视频，链接在这里有兴趣的可以参考。https://www.youtube.com/watch?v=q6IEA26hvXc


文字的描述如下：
这个算法如果想要整合一起之后进行计算的话，这样的确可以出结果，就像我写的那样。但是题目要求是log(m+n)的时间复杂度。这就很明显不符合要求了。根据复杂度判断，很可能是要求我们使用二分法。
我们想要找到中间值，可以变相理解成是需要把整合完成的数组分割成两个数组(left and right)。我们可以先将所有的left里面的元素都规划在最长的数组n1里面(即 l1=(m+n)/2 , l1是n1在left里面的最后一个元素的下标)，n2此时在left里面的元素为NUL，即l2(n2在left里面的下标)=0。
我们比较n1[l1] 与 n2[l2+1]， n2[l2] 与 n1[l1+1]。我们需要保证n1[l1] <= n2[l2+1]，n2[l2] <= n1[l1+1]。只有这样才能保证left里面的数值都比right里面的小。
通过这种方式我们找到了left和right分别在n1和n2里面的分界点。我们比较left的rightmost和right里面的leftmost。
当总元素数量为偶数时：
(max(l1, l2) + min(r1, r2)) / 2
当总元素数量为基数时：
max(l1, l2)

我个人感觉这种不应该算是二分查找法。别人都是这么称呼的。那就这么称呼吧。

果然hard的题目会稍微难一些。对时间复杂度还有要求。