江川个人博客FIELD NOTES / 个人知识库

Article / 文章

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 算法的时间复杂度应该为 O(log (m+n))。

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n))。

难度

困难

题目链接

https://leetcode.cn/problems/median-of-two-sorted-arrays/

示例

示例 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
  • -106 <= nums1[i], nums2[i] <= 106

解题思路

方法一：二分查找

要达到 O(log(m+n)) 的时间复杂度，必须使用二分查找。关键是将问题转化为寻找第k小的数的问题。

关键点：

  1. 中位数的定义：
    • 当总长度为奇数时，中位数是第 (m+n)/2 + 1 个数
    • 当总长度为偶数时，中位数是第 (m+n)/2 和第 (m+n)/2 + 1 个数的平均值
  2. 使用二分查找来寻找第k小的数
  3. 每次比较两个数组的第 k/2 个数，排除掉不可能的部分

具体步骤：

  1. 确定中位数的位置k
  2. 在两个数组中进行二分查找：
    • 比较两个数组中第 k/2 个数的大小
    • 较小的那部分不可能包含第k小的数
    • 排除较小的部分，继续查找剩余部分
  3. 递归进行上述过程，直到找到目标数

时间复杂度：O(log(m+n)) 空间复杂度：O(1)

方法二：划分数组（更优解）

这个方法的思路是将两个数组分别划分，使得：

  • 左半部分的长度等于右半部分
  • 左半部分的最大值小于等于右半部分的最小值

代码实现

C# 实现（二分查找）

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.Length + nums2.Length;
        if (totalLength % 2 == 1) {
            return FindKth(nums1, 0, nums2, 0, totalLength / 2 + 1);
        } else {
            return (FindKth(nums1, 0, nums2, 0, totalLength / 2) + 
                   FindKth(nums1, 0, nums2, 0, totalLength / 2 + 1)) / 2.0;
        }
    }
    
    private double FindKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
        // 如果数组1已经用完，直接从数组2中返回第k个数
        if (start1 >= nums1.Length) {
            return nums2[start2 + k - 1];
        }
        // 如果数组2已经用完，直接从数组1中返回第k个数
        if (start2 >= nums2.Length) {
            return nums1[start1 + k - 1];
        }
        // 如果k=1，返回两个数组开头较小的数
        if (k == 1) {
            return Math.Min(nums1[start1], nums2[start2]);
        }
        
        // 比较两个数组中第k/2个数的大小
        int mid1 = start1 + k/2 - 1 < nums1.Length ? 
                  nums1[start1 + k/2 - 1] : int.MaxValue;
        int mid2 = start2 + k/2 - 1 < nums2.Length ? 
                  nums2[start2 + k/2 - 1] : int.MaxValue;
        
        if (mid1 < mid2) {
            // 排除nums1的前k/2个数
            return FindKth(nums1, start1 + k/2, nums2, start2, k - k/2);
        } else {
            // 排除nums2的前k/2个数
            return FindKth(nums1, start1, nums2, start2 + k/2, k - k/2);
        }
    }
}

C# 实现（划分数组）

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组
        if (nums1.Length > nums2.Length) {
            return FindMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.Length;
        int n = nums2.Length;
        int left = 0;
        int right = m;
        
        while (left <= right) {
            // nums1 的分割线
            int i = (left + right) / 2;
            // nums2 的分割线
            int j = (m + n + 1) / 2 - i;
            
            // nums1 分割线左边的值
            int nums1LeftMax = (i == 0) ? int.MinValue : nums1[i - 1];
            // nums1 分割线右边的值
            int nums1RightMin = (i == m) ? int.MaxValue : nums1[i];
            // nums2 分割线左边的值
            int nums2LeftMax = (j == 0) ? int.MinValue : nums2[j - 1];
            // nums2 分割线右边的值
            int nums2RightMin = (j == n) ? int.MaxValue : nums2[j];
            
            // 找到合适的分割线
            if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
                // 如果是奇数个元素
                if ((m + n) % 2 == 1) {
                    return Math.Max(nums1LeftMax, nums2LeftMax);
                }
                // 如果是偶数个元素
                else {
                    return (Math.Max(nums1LeftMax, nums2LeftMax) + 
                           Math.Min(nums1RightMin, nums2RightMin)) / 2.0;
                }
            }
            // 需要调整分割线
            else if (nums1LeftMax > nums2RightMin) {
                right = i - 1;
            }
            else {
                left = i + 1;
            }
        }
        
        throw new ArgumentException("Input arrays are not sorted");
    }
}

划分数组方法详解

  1. 基本思想：

    • 在较短的数组上二分查找分割线位置
    • 保证左半部分和右半部分的元素个数相等（或左边比右边多一个）
    • 确保左半部分的最大值小于等于右半部分的最小值

  2. 关键步骤：

    • 确保nums1是较短的数组，减少查找范围
    • 通过二分查找确定nums1的分割线位置i
    • 根据i计算nums2的分割线位置j
    • 比较分割线两侧的值，判断是否找到正确位置

  3. 边界处理：

    • 使用int.MinValue和int.MaxValue处理分割线在数组边界的情况
    • 考虑总长度为奇数和偶数的不同情况
    • 处理数组为空的特殊情况

  4. 时间复杂度分析：

    • 总体时间复杂度：O(log(min(m,n)))
    • 空间复杂度：O(1)

执行结果（划分数组方法）：

  • 执行用时：84 ms
  • 内存消耗：50.8 MB

两种方法比较：

  1. 时间复杂度：

    • 二分查找：O(log(m+n))
    • 划分数组：O(log(min(m,n)))，更优

  2. 空间复杂度：

    • 两种方法都是O(1)

  3. 代码复杂度：

    • 二分查找：实现较简单，思路直观
    • 划分数组：实现较复杂，但效率更高

  4. 适用场景：

    • 二分查找：更通用，容易理解
    • 划分数组：特别适合处理有序数组的中位数问题

代码详解

  1. totalLength % 2 == 1：判断总长度是奇数还是偶数
  2. FindKth方法：查找第k小的数
    • 处理边界情况：某个数组用完或k=1
    • 比较两个数组中第k/2个数的大小
    • 排除较小的部分，继续递归查找
  3. int.MaxValue：处理数组长度不足k/2的情况
  4. 递归调用时更新起始位置和k值

执行结果

  • 执行用时：92 ms
  • 内存消耗：51.2 MB

总结与反思

  1. 这是一道经典的困难题目，考察了：
    • 二分查找的应用
    • 分治思想
    • 边界情况的处理
  2. 关键点：
    • 理解中位数的定义
    • 正确处理奇偶长度的情况
    • 高效排除不可能的部分
  3. 优化思路：
    • 可以通过划分数组的方法进一步优化
    • 注意特殊情况的处理

相关题目