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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

看到时间复杂度为 O(log(m+n))，理所当然的想到，小根堆（大根堆）

因为构建根堆的时间复杂度就是 log(N)。

当然，如果没有这个条件限制，那么会产生以下的思考。

姿势 1

直接整合排序找中位数：

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

简单粗暴，但是时间复杂度肯定不符合要求，虽然跑测试通过了。

可能在调用自带的 sort 方法的时候会自动做优化，但是肯定也不符合要求。

sort 与 sorted 区别：

sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。

list 的 sort 方法返回的是对已经存在的列表进行操作，无返回值，而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作。

姿势 2

再就想到的是将两个列表整合起来排序，由于是两个有序数组，可以使用链表的合并。

优化一点就是，合并到中位数就停止。

有序链表的合并属于数据结构基础知识，不再赘述。

时间复杂度肯定不达标，大概是 O(N)

姿势 3

正主，小根堆。

借助的是 heapq 实现小根堆。

这个肯定是符合时间复杂度要求的，但是这个效率和内存不太满意。

import heapq


class TopkHeap(object):
   def __init__(self, k):
       self.k = k
       self.data = []

   def push(self, elem):
       if len(self.data) < self.k:
           heapq.heappush(self.data, elem)
       else:
           topk_small = self.data[0]
           if elem > topk_small:
               heapq.heapreplace(self.data, elem)

   def TopK(self):
        return [x for x in reversed([heapq.heappop(self.data) for x in range(len(self.data))])]



class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1 = len(nums1)
        len2 = len(nums2)
        nums = nums1+nums2
        # 如果即奇数个，则直接取中位数，也就是第k大的值
        if (len1+len2) % 2 != 0:
            k = int((len1+len2)/2+1)
            th = TopkHeap(k)
            for i in nums:
                th.push(i)
            return th.TopK()[-1]
        # 如果是偶数个
        else:
            k = int((len1+len2)/2+1)
            th = TopkHeap(k)
            for i in nums:
                th.push(i)
            data = th.TopK()
            return (data[-1]+data[-2])/2

姿势 4

官方说的，二分法？没怎么看懂。感觉还是比较复杂的。

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

这个回答挺好的。但是我没法复述了。。。