Median of Two Sorted Arrays

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

分析

采用二分查找的方法，避免直接合并数组：

总长度奇偶性判断：
- 如果两个数组合并后的长度为奇数，只需找到第 total / 2 + 1 小的数
- 如果为偶数，需找到第 total / 2 和第 total / 2 + 1 小的数，然后取平均值
递归查找第 k 小的数：
- 边界条件（递归终止条件）：
  - 如果一个数组为空，直接返回另一个数组中的第 k 小的数
  - 如果 k = 1，返回两个数组当前起点的较小值
- 二分递归：
  - 比较两个数组中第 k / 2 小的元素
  - 较小的那一部分不可能包含第 k 小的数，因此可以直接从数组中排除
  - 递归更新起始位置和 k 的值

时间复杂度

每次递归将搜索范围缩小一半，因此时间复杂度为 O(log(min(m, n)))

空间复杂度

空间复杂度为递归调用的栈空间，最大为 O(log(min(m, n)))

C++代码

 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
34
35
36
37
38
39
40
41
42
43
44
45
46


class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        // 计算总长度
        int total = nums1.size() + nums2.size();

        // 如果总长度为偶数，需找到中间两个数并取平均值
        if (total % 2 == 0)
        {
            double left = find(nums1, 0, nums2, 0, total / 2);
            double right = find(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2;
        }

        // 如果总长度为奇数，找到中间的数
        return find(nums1, 0, nums2, 0, total / 2 + 1);
    }

    double find(std::vector<int>& nums1, int i, std::vector<int>& nums2, int j, int k)
    {
        // 让 nums1 始终是较短的数组
        if (nums1.size() - i > nums2.size() - j)
            return find(nums2, j, nums1, i, k);

        // 边界条件：nums1 已经为空
        if (nums1.size() - i == 0)
            return nums2[j + k - 1];

        // 边界条件：k = 1，直接返回两数组当前起点的较小值
        if (k == 1)
            return std::min(nums1[i], nums2[j]);

        // 二分查找
        int mid1 = std::min((int)nums1.size() - 1, i + k / 2 - 1);
        int mid2 = j + k / 2 - 1;

        if (nums1[mid1] > nums2[mid2])
            // 排除 nums2 前 (mid2 - j + 1) 个元素
            return find(nums1, i, nums2, mid2 + 1, k - (mid2 - j + 1));
        else
            // 排除 nums1 前 (mid1 - i + 1) 个元素
            return find(nums1, mid1 + 1, nums2, j, k - (mid1 - i + 1));
    }
};