【面试题】寻找两个正序数组的中位数

寻找两个正序数组的中位数

面试学习

给定两个大小分别为 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

五、复杂度分析

• 时间复杂度：O(log(min(m, n)))，在较小数组上进行二分查找。
• 空间复杂度：O(1)，只使用常数额外空间。

六、代码

寻找两个正序数组的中位数