1. 题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 。请你找出并返回这两个正序数组的中位数 。要求总的时间复杂度必须为 $O (l o g (m + n))$ 。

1.1 示例

示例 1：

输入： nums1 = [1, 3] ， nums2 = [2]
输出： $2.00000$
解释： 合并数组 = [1, 2, 3] ，中位数 $2$

示例 2：

输入： nums1 = [1, 2] ， nums2 = [3, 4]
输出： $2.50000$
解释： 合并数组 = [1, 2, 3, 4] ，中位数 $(2 + 3) / 2 = 2.5$

示例 3：

输入： nums1 = [0, 0] ， nums2 = [0, 0]
输出： $0.00000$

示例 4：

输入： nums1 = [] ， nums2 = [1]
输出： $1.00000$

示例 5：

输入： nums1 = [2] ， nums2 = []
输出： $2.00000$

1.2 说明

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

1.3 提示

$n u m s 1 . l e n g t h = = m$
$n u m s 2 . l e n g t h = = n$
$\le m \le 1000$
$\le n \le 1000$
$\le m + n \le 2000$
$-10^6 \le nums1[i], nums2[i] \le 10^6$

2. 题解一（堆排序）

2.1 分析

先排序再计算中位数。

2.2 解答

from typing import List


class Solution:
    def _down_heap(self, arr: List[int], num, j):
        """
        通过元素交换，确保列表arr[0:num]中，元素arr[j]及其子孙节点满足堆序性质
        :param arr: 列表形式给出的待排序列
        :param num: 列表索引上限
        :param j: 列表元素的索引
        :return: None
        """
        left = 2 * j + 1  # 元素arr[j]左子节点的索引
        right = 2 * j + 2  # 元素arr[j]右子节点的索引
        if left < num:  # 判断arr[j]是否有左子节点
            large_child = left
            if right < num:  # 判断arr[j]是否有右子节点
                if arr[right] > arr[left]:
                    large_child = right
            if arr[large_child] > arr[j]:  # 确保最终建成最大堆
                arr[large_child], arr[j] = arr[j], arr[large_child]  # 交换两个节点处的值使满足堆序性质
                self._down_heap(arr, num, large_child)

    def heapify(self, arr: List[int]):
        """将列表形式给出的元素视为完全二叉树，对其进行建堆"""
        for j in range((len(arr) - 1) // 2, -1, -1):  # 建堆
            self._down_heap(arr, len(arr), j)

    def heap_sort(self, arr: List[int]):
        """堆排序"""
        self.heapify(arr)  # 构建最大堆
        # 依次将最大值，次大值...最小值从右往左排好
        for i in range(len(arr) - 1, 0, -1):  # 到0而非-1是为了避免下面出现arr[0], arr[0] = arr[0], arr[0]这一无谓操作
            arr[i], arr[0] = arr[0], arr[i]  # 每一次迭代，将当前堆中最大元素排好序
            self._down_heap(arr, i, 0)  # 每迭代一次后第i+1个元素arr[i]已排好序，仅需确保前i个元素满足堆序性质

    def find_median_sorted_arrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1 + nums2
        self.heapify(nums)
        self.heap_sort(nums)
        if len(nums) % 2 == 1:
            return float(nums[len(nums) // 2])
        else:
            return float((nums[len(nums) // 2 - 1] + nums[len(nums) // 2]) / 2)


def main():
    sln = Solution()
    nums1 = [1, 3]
    nums2 = [2]
    print(sln.find_median_sorted_arrays(nums1, nums2))  # 2.0


if __name__ == '__main__':
    main()