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

力扣题目链接 (opens new window)

题目描述

给定两个大小分别为 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

思路

要求时间复杂度 O(log(m+n))，看到 log 就应该想到二分查找。

方法一：合并后找中位数（不推荐）

最直观的想法是合并两个数组，然后找中位数。时间复杂度 O(m+n)，不符合题目要求。

虽然不符合要求，但可以作为思路的起点。

方法二：二分查找第 k 小的数

换个角度思考：中位数是什么？

• 如果总长度是奇数，中位数是第 (m+n+1)/2 小的数
• 如果总长度是偶数，中位数是第 (m+n)/2 和第 (m+n)/2+1 小的数的平均值

所以问题转化为：在两个有序数组中找第 k 小的数。

怎么用二分查找？

每次比较两个数组的第 k/2 个元素：

• 如果 nums1[k/2-1] < nums2[k/2-1]，说明 nums1 的前 k/2 个元素一定不是第 k 小的数，可以排除
• 反之，排除 nums2 的前 k/2 个元素

每次排除 k/2 个元素，k 不断减半，时间复杂度 O(log k) = O(log(m+n))。

边界处理：

1. 如果某个数组已经全部排除，直接返回另一个数组的第 k 个元素
2. 如果 k = 1，返回两个数组当前位置的最小值
3. 如果某个数组剩余长度 < k/2，取该数组的最后一个元素比较

方法三：划分数组（更优雅）

还有一种更优雅的思路：把两个数组划分成左右两部分，使得：

• 左半部分的所有元素 ≤ 右半部分的所有元素
• 左右两部分的元素个数相等（或左边比右边多 1 个）

这种方法更难理解，但代码更简洁。这里以"找第 k 小"的方法为主讲解。

模拟过程

以示例 1 为例：nums1 = [1,3], nums2 = [2]

总长度 = 3，是奇数，找第 (3+1)/2 = 2 小的数。

第一步：比较第 k/2 = 1 个元素

• nums1[0] = 1
• nums2[0] = 2
• 1 < 2，排除 nums1 的前 1 个元素

第二步：k = 1，直接返回两个数组当前位置的最小值

• nums1[1] = 3
• nums2[0] = 2
• 返回 min(3, 2) = 2

---

以示例 2 为例：nums1 = [1,2], nums2 = [3,4]

总长度 = 4，是偶数，需要找第 2 和第 3 小的数。

先找第 2 小：

第一步：比较第 k/2 = 1 个元素

• nums1[0] = 1
• nums2[0] = 3
• 1 < 3，排除 nums1[0]

第二步：k = 1，返回 min(2, 3) = 2

再找第 3 小（类似过程），得到 3。

中位数 = (2 + 3) / 2 = 2.5

解题代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int total = m + n;
        
        if (total % 2 == 1) {
            // 奇数，找第 (total+1)/2 小的数
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        } else {
            // 偶数，找第 total/2 和 total/2+1 小的数
            int left = findKth(nums1, 0, nums2, 0, total / 2);
            int right = findKth(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
    }
    
private:
    // 在 nums1[start1...] 和 nums2[start2...] 中找第 k 小的数
    int findKth(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k) {
        // 边界1：nums1 已经全部排除
        if (start1 >= nums1.size()) {
            return nums2[start2 + k - 1];
        }
        // 边界2：nums2 已经全部排除
        if (start2 >= nums2.size()) {
            return nums1[start1 + k - 1];
        }
        // 边界3：k = 1，返回两个数组当前位置的最小值
        if (k == 1) {
            return min(nums1[start1], nums2[start2]);
        }
        
        // 比较第 k/2 个元素
        int half = k / 2;
        int mid1 = start1 + half - 1 < nums1.size() ? nums1[start1 + half - 1] : INT_MAX;
        int mid2 = start2 + half - 1 < nums2.size() ? nums2[start2 + half - 1] : INT_MAX;
        
        if (mid1 < mid2) {
            // 排除 nums1 的前 k/2 个元素
            return findKth(nums1, start1 + half, nums2, start2, k - half);
        } else {
            // 排除 nums2 的前 k/2 个元素
            return findKth(nums1, start1, nums2, start2 + half, k - half);
        }
    }
};

复杂度分析

• 时间复杂度：O(log(m+n))，每次排除 k/2 个元素
• 空间复杂度：O(log(m+n))，递归调用栈

其他语言

Python3

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        total = m + n
        
        def findKth(start1, start2, k):
            # 边界处理
            if start1 >= m:
                return nums2[start2 + k - 1]
            if start2 >= n:
                return nums1[start1 + k - 1]
            if k == 1:
                return min(nums1[start1], nums2[start2])
            
            # 比较第 k/2 个元素
            half = k // 2
            mid1 = nums1[start1 + half - 1] if start1 + half - 1 < m else float('inf')
            mid2 = nums2[start2 + half - 1] if start2 + half - 1 < n else float('inf')
            
            if mid1 < mid2:
                return findKth(start1 + half, start2, k - half)
            else:
                return findKth(start1, start2 + half, k - half)
        
        if total % 2 == 1:
            return findKth(0, 0, total // 2 + 1)
        else:
            left = findKth(0, 0, total // 2)
            right = findKth(0, 0, total // 2 + 1)
            return (left + right) / 2.0

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int total = m + n;
        
        if (total % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        } else {
            int left = findKth(nums1, 0, nums2, 0, total / 2);
            int right = findKth(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
    }
    
    private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
        if (start1 >= nums1.length) {
            return nums2[start2 + k - 1];
        }
        if (start2 >= nums2.length) {
            return nums1[start1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        
        int half = k / 2;
        int mid1 = start1 + half - 1 < nums1.length ? nums1[start1 + half - 1] : Integer.MAX_VALUE;
        int mid2 = start2 + half - 1 < nums2.length ? nums2[start2 + half - 1] : Integer.MAX_VALUE;
        
        if (mid1 < mid2) {
            return findKth(nums1, start1 + half, nums2, start2, k - half);
        } else {
            return findKth(nums1, start1, nums2, start2 + half, k - half);
        }
    }
}

Go

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    total := m + n
    
    findKth := func(start1, start2, k int) int {
        for {
            if start1 >= m {
                return nums2[start2+k-1]
            }
            if start2 >= n {
                return nums1[start1+k-1]
            }
            if k == 1 {
                if nums1[start1] < nums2[start2] {
                    return nums1[start1]
                }
                return nums2[start2]
            }
            
            half := k / 2
            mid1, mid2 := math.MaxInt32, math.MaxInt32
            if start1+half-1 < m {
                mid1 = nums1[start1+half-1]
            }
            if start2+half-1 < n {
                mid2 = nums2[start2+half-1]
            }
            
            if mid1 < mid2 {
                start1 += half
            } else {
                start2 += half
            }
            k -= half
        }
    }
    
    if total%2 == 1 {
        return float64(findKth(0, 0, total/2+1))
    } else {
        left := findKth(0, 0, total/2)
        right := findKth(0, 0, total/2+1)
        return float64(left+right) / 2.0
    }
}

JS

var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const total = m + n;
    
    const findKth = (start1, start2, k) => {
        if (start1 >= m) {
            return nums2[start2 + k - 1];
        }
        if (start2 >= n) {
            return nums1[start1 + k - 1];
        }
        if (k === 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        
        const half = Math.floor(k / 2);
        const mid1 = start1 + half - 1 < m ? nums1[start1 + half - 1] : Infinity;
        const mid2 = start2 + half - 1 < n ? nums2[start2 + half - 1] : Infinity;
        
        if (mid1 < mid2) {
            return findKth(start1 + half, start2, k - half);
        } else {
            return findKth(start1, start2 + half, k - half);
        }
    };
    
    if (total % 2 === 1) {
        return findKth(0, 0, Math.floor(total / 2) + 1);
    } else {
        const left = findKth(0, 0, total / 2);
        const right = findKth(0, 0, total / 2 + 1);
        return (left + right) / 2.0;
    }
};

与代码随想录联系

这道题是二分查找的经典难题，也是面试中的 hard 题。

在代码随想录 二分查找章节 中，详细讲过二分查找的思想和模板。

本题的难点：

1. 问题转化 — 从"找中位数"转化为"找第 k 小的数"
2. 二分的对象 — 不是在单个数组中二分，而是每次排除 k/2 个元素
3. 边界处理 — 数组用完、k=1、剩余长度不足 k/2 等多种情况

很多录友看到这道题，第一反应是合并数组再找中位数。但题目要求 O(log(m+n))，就是在提示你用二分。

二分查找的核心是"每次排除一半"。这道题虽然不是在单个数组中二分，但每次也是排除 k/2 个元素，k 不断减半，符合二分的思想。

建议录友们先把基础的二分查找题目做透，理解二分的本质，再来挑战这道题会更容易理解。