LeetCode 刷题：4. 寻找两个正序数组的中位数

这题常规思路简单，但如果要达到官方要求的时间复杂度是比较难想的。

标题	寻找两个正序数组的中位数
序号	NO.4
难度	困难
标签	数组 二分查找 分治

1. 题目

---

给定两个大小分别为 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<sup>6 <= nums1[i], nums2[i] <= 10</sup>6

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 代码

---

方法一

中位数是指数组中处在中间的位置的数，也就是在含有 n 个数的数组中，从小到大排列第 n/2 个数。只需要每次在这两个数组中选取一个值比较小的数，第 (m+n)/2 个数即为中位数，注意总数为偶数情况下，需要求平均值。这个方法需要查找 (m+n)/2 次，比合并数组节约一半时间，但仍未达到题目要求的时间复杂度 O (log (m+n))。

• 时间复杂度 O (m+n)

• 空间复杂度 O (1)

• 执行用时：52 ms, 在所有 Python3 提交中击败了 39.50% 的用户

• 内存消耗：15.2 MB, 在所有 Python3 提交中击败了 33.89% 的用户

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        i, j, k = 1, 0, 0  # 记录数组位置
        median = pre = 0  # 中位数

        while (i <= (m+n)/2+1):  # 查找两个数组中第 i 小的数
            pre = median
            if (j < m and k < n and (nums1[j] < nums2[k]) or k == n):
                median = nums1[j]
                j += 1
            elif (j < m and k < n and (nums1[j] >= nums2[k]) or j == m):
                median = nums2[k]
                k += 1
            i += 1

        if ((m+n) % 2 == 0):
            median = (median + pre) / 2

        return median

• 执行用时：8 ms, 在所有 C 提交中击败了 97.53% 的用户
• 内存消耗：6.3 MB, 在所有 C 提交中击败了 56.65% 的用户

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int i = 1, j = 0, k = 0;  // 记录数组位置
    double median = 0, pre = 0;  // 中位数
    while (i <= (nums1Size + nums2Size) / 2 + 1)  // 查找两个数组中第 i 小的数
    {
        pre = median;
        if ((j < nums1Size && k < nums2Size && nums1[j] < nums2[k]) || k == nums2Size)
        {
            median = nums1[j];
            j += 1;
        }
        else if ((j < nums1Size && k < nums2Size && nums1[j] >= nums2[k]) || j == nums1Size)
        {
            median = nums2[k];
            k += 1;
        }
        i++;
    }
    if ((nums1Size + nums2Size) % 2 == 0)
        median = (median + pre) / 2;
    return median;
}

方法二

看到时间复杂度要求是 log 级，所以肯定要使用二分法。方法待补充

• 时间复杂度 O (log (m+n))

• 空间复杂度 O (1)

• 执行用时：ms

• 内存消耗：MB

• 执行用时：ms

• 内存消耗：MB