寻找两个正序数组的中位数
面试学习
给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2，我们需要找到这两个数组的中位数。下面是详细的解题步骤和 Python 代码示例。
一、问题描述
一、问题描述
我们需要在两个有序数组中找到中位数，确保算法的时间复杂度为 O(log(min(m, n)))。
二、解题思路
2.1 确保第一个数组较小
始终在较小的数组上进行二分查找，以确保时间复杂度最优。
2.2 进行二分查找
- 定义分割点 i 在 nums1 中，分割点 j 在 nums2 中，使得 i + j 为两个数组的中位数所需的总元素数的一半。
- 根据分割点的选择，确保 nums1[i - 1] <= nums2[j] 和 nums2[j - 1] <= nums1[i] 这两个条件成立。
2.3 计算中位数
- 如果满足上述条件，则找到中位数：
- 如果总元素数为偶数，中位数为 (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) /2
- 如果总元素数为奇数，中位数为 max(nums1[i-1], nums2[j-1])。
三、详细步骤
3.1 初始化
- 确保 nums1 是较小的数组。
3.2 进行二分查找
- 定义变量 m 和 n 为两个数组的长度。
- 使用二分查找在 nums1 上进行搜索，设定 left 和 right 为数组的边界。
3.3 调整分割点
- 根据条件不断调整分割点，直到找到合适的分割。
3.4 返回中位数
- 根据总元素的奇偶性返回中位数。
四、Python 代码示例
def findMedianSortedArrays(nums1, nums2): m, n = len(nums1), len(nums2) if m > n: nums1, nums2, m, n = nums2, nums1, n, m left, right = 0, m half_len = (m + n + 1) // 2 while left <= right: i = (left + right) // 2 j = half_len - i if i < m and nums1[i] < nums2[j - 1]: left = i + 1 elif i > 0 and nums1[i - 1] > nums2[j]: right = i - 1 else: max_of_left = 0 if i == 0: max_of_left = nums2[j - 1] elif j == 0: max_of_left = nums1[i - 1] else: max_of_left = max(nums1[i - 1], nums2[j - 1]) if (m + n) % 2 == 1: return max_of_left min_of_right = 0 if i == m: min_of_right = nums2[j] elif j == n: min_of_right = nums1[i] else: min_of_right = min(nums1[i], nums2[j]) return (max_of_left + min_of_right) / 2.0 return 0.0 # should never reach here
五、复杂度分析
- 时间复杂度：O(log(min(m, n)))，在较小数组上进行二分查找。
- 空间复杂度：O(1)，只使用常数额外空间。
