--- title: 4. 寻找两个正序数组的中位数 description: 合并两个有序数组后找出中位数，要求时间复杂度为 O(log (m+n))。 date: 2024-03-14 tag: [困难, 数组, 二分查找] author: Easy Algo premium: false percentage: 30 --- ## 题目 4 > leetcode 链接：[寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/) 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (m+n)) 。 **示例 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 ``` **提示：** ``` 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` 为空数组 * `nums1` 和 `nums2` 都为空数组（虽然题目中 `m + n >= 1`，但考虑完整性） * 一个数组的所有元素都小于/大于另一个数组的所有元素 * **测试用例：** * `nums1 = [1, 3], nums2 = [2]`，输出：`2.0` * `nums1 = [1, 2], nums2 = [3, 4]`，输出：`2.5` * `nums1 = [ ], nums2 = [1, 2, 3]`，输出：`2.0` * `nums1 = [1, 2], nums2 = []`，输出：`1.5` * `nums1 = [1, 5], nums2 = [2, 3, 4]`，输出：`3.0` * `nums1 = [1, 2], nums2 = [1, 2, 3]`，输出：`2.0` **解法分析：** | 解法 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 | | ---------------- | -------------------------------------------------------------------- | ------------------------------------------------------------------ | -------- | -------- | | 合并后排序 | 简单易懂 | 时间复杂度高，不符合题目要求 | O(m+n)log(m+n) | O(m+n) | | 双指针 | 无需额外空间，思路简单 | 时间复杂度较高，不符合题目要求 | O(m+n) | O(1) | | 二分查找（推荐） | 时间复杂度符合题目要求，效率高 | 理解稍有难度 | O(log(min(m,n))) | O(1) | **复杂度评估方法：** * **时间复杂度：** 衡量算法执行时间随输入规模增长的速度。 * **空间复杂度：** 衡量算法所需额外空间随输入规模增长的速度。 * O(log n) 通常表示算法使用了分治法，每次将问题规模缩小一半。 **推荐解法：** 二分查找 **Python代码实现：** **版本一：含详细注释** ```python def findMedianSortedArrays(nums1, nums2): """ 寻找两个正序数组的中位数 Args: nums1: 第一个正序数组 nums2: 第二个正序数组 Returns: 两个数组的中位数 """ # 为了保证二分查找的效率，我们始终让 nums1 是较短的数组 if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) low, high = 0, m while low <= high: # i 是 nums1 的分割线，j 是 nums2 的分割线 # 分割线左边的元素个数之和等于 (m + n + 1) / 2 i = (low + high) // 2 j = (m + n + 1) // 2 - i # 找到分割线后，需要考虑边界情况 max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1] min_right_nums1 = float('inf') if i == m else nums1[i] max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1] min_right_nums2 = float('inf') if j == n else nums2[j] # 如果满足条件，说明分割线找到了 if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1: # 如果 m + n 是偶数，中位数是左边最大值和右边最小值的平均值 if (m + n) % 2 == 0: return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2 # 如果 m + n 是奇数，中位数是左边最大的值 else: return max(max_left_nums1, max_left_nums2) # 如果 nums1 的左边最大值大于 nums2 的右边最小值，说明 nums1 的分割线太靠右了，需要向左移动 elif max_left_nums1 > min_right_nums2: high = i - 1 # 否则，nums1 的分割线太靠左了，需要向右移动 else: low = i + 1 ``` **版本二：去除注释** ```python def findMedianSortedArrays(nums1, nums2): if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) low, high = 0, m while low <= high: i = (low + high) // 2 j = (m + n + 1) // 2 - i max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1] min_right_nums1 = float('inf') if i == m else nums1[i] max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1] min_right_nums2 = float('inf') if j == n else nums2[j] if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1: if (m + n) % 2 == 0: return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2 else: return max(max_left_nums1, max_left_nums2) elif max_left_nums1 > min_right_nums2: high = i - 1 else: low = i + 1 ``` **代码运行过程详细描述：** 1. **确保 `nums1` 较短：** 如果 `nums1` 比 `nums2` 长，交换它们，以保证二分查找在较短的数组上进行，提高效率。 2. **初始化变量：** `m` 和 `n` 分别是 `nums1` 和 `nums2` 的长度。`low` 和 `high` 用于二分查找，初始化为 `0` 和 `m`。 3. **二分查找：** * 循环条件：`low <= high`。 * 计算 `i` 和 `j`：`i` 是 `nums1` 的分割线，`j` 是 `nums2` 的分割线。`i` 和 `j` 的选择需要保证 `i + j = (m + n + 1) // 2`，这意味着分割线左边的元素总数等于 `(m + n + 1) / 2`。 * 处理边界情况：当 `i` 或 `j` 为 0 或 `m`/`n` 时，需要将左边的最大值设为负无穷，右边的最小值设为正无穷，以避免数组越界。 * 检查分割线是否正确：如果 `max_left_nums1 <= min_right_nums2` 且 `max_left_nums2 <= min_right_nums1`，说明分割线找到了正确的位置。 * 如果 `m + n` 是偶数，中位数是 `(max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2`。 * 如果 `m + n` 是奇数，中位数是 `max(max_left_nums1, max_left_nums2)`。 * 调整二分查找的范围： * 如果 `max_left_nums1 > min_right_nums2`，说明 `nums1` 的分割线太靠右了，需要将 `high` 设为 `i - 1`。 * 否则，说明 `nums1` 的分割线太靠左了，需要将 `low` 设为 `i + 1`。 4. **返回值：** 找到中位数后，直接返回。希望这个解答能够帮助你理解这道题目！