题解链接

Leetcode 4.寻找两个正序数组的中位数

题目描述

给定两个大小分别为 $m$ 和 $n$ 的正序数组 $nums1$ 和 $nums2$。

请你找出并返回这两个正序数组合并后的中位数。

算法的时间复杂度应为 $O(log(m+n))$。

中位数定义如下：

如果合并后的数组长度为奇数，则中位数为中间的那个数。

如果合并后的数组长度为偶数，则中位数为中间两个数的平均值。

输入描述

第一行输入两个整数 $m$ 和 $n$，分别表示数组 $nums1$ 和数组 $nums2$ 的长度。

第二行输入 $m$ 个整数，表示正序数组 $nums1$ 中的元素。

第三行输入 $n$ 个整数，表示正序数组 $nums2$ 中的元素。

如果某个数组长度为 $0$，则对应行为空行。

输出描述

输出一个浮点数，表示两个正序数组合并后的中位数。

结果保留 $5$ 位小数。

样例 $1$

输入

2 1
1 3
2

输出

2.00000

样例解释

合并数组为 $[1, 2, 3]$，中位数为 $2$。

样例 $2$

输入

2 2
1 2
3 4

输出

2.50000

样例解释

合并数组为 $[1, 2, 3, 4]$，中位数为 $(2 + 3) / 2 = 2.5$。

数据范围

$nums1.length == m$

$nums2.length == n$

$0 <= m <= 1000$

$0 <= n <= 1000$

$1 <= m + n <= 2000$

$-10^6 <= nums1[i], nums2[i] <= 10^6$

$nums1$ 和 $nums2$ 均为正序数组。