忍者算法

Appearance

探秘算法之巅：寻找两个有序数组的中位数！ ​

大家好，我是忍者算法。今天我们要挑战一道 LeetCode 难度系数最高的题目之一 - LeetCode 4「寻找两个正序数组的中位数」。这道题不仅考察我们对二分查找的理解，更要求我们具备深入的数学思维。让我们一起攻克这个难题！

📚 从生活场景切入 ​

想象你是一位体育老师，手里有两份不同班级的体测成绩单，都已经按照分数排序。现在你需要找出这两个班级所有同学成绩的中间水平。直观的做法是把两个成绩单合并后重新排序，但这样效率太低。其实我们可以用更聪明的方法，这就是今天要讨论的问题。

💡 问题解析 ​

题目要求： 给定两个有序数组 nums1 和 nums2，要求找出这两个数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

示例：

java
输入：nums1 = [1,3], nums2 = [2]
输出：2.0
解释：合并数组 = [1,2,3]，中位数是 2.0

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.5
解释：合并数组 = [1,2,3,4]，中位数是 (2 + 3) / 2 = 2.5

🤔 思路发展历程 ​

1. 直观思路（不符合要求） ​

最简单的方法是合并两个数组后找中位数，但时间复杂度是 O(m+n)，不满足题目要求。

2. 优化思路 ​

我们可以转化思路：不需要真正合并数组，只需要找到第 (m+n)/2 小的元素（或者在偶数情况下找第 (m+n)/2 和 (m+n)/2+1 小的元素）。这启发我们使用二分查找来定位这个位置。

🚀 优雅的解决方案 ​

java
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 确保 nums1 是较短的数组，优化性能
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        
        int m = nums1.length;
        int n = nums2.length;
        
        // 在 nums1 的区间 [0, m] 中查找恰当的分割线
        int left = 0;
        int right = m;
        
        while (left <= right) {
            // nums1 的分割线
            int i = (left + right) / 2;
            // nums2 的分割线
            int j = (m + n + 1) / 2 - i;
            
            // 获取分割线左右的元素
            double maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            double minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            double maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            double minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            
            // 判断是否找到了正确的分割线
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 找到合适的分割线，计算中位数
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + 
                            Math.min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            }
            // 调整搜索范围
            else if (maxLeft1 > minRight2) {
                right = i - 1;
            }
            else {
                left = i + 1;
            }
        }
        
        throw new IllegalArgumentException("输入数组不合法");
    }
}

📝 代码详解 ​

让我们深入理解这个解决方案的精妙之处：

1. 核心思想 ​

我们要找的是一个位置，将两个数组分别分成左右两部分，使得：

  • 左半部分的元素都小于右半部分
  • 左半部分的元素个数等于右半部分（或比右半部分多1个）

2. 关键步骤解析 ​

A. 预处理

  • 确保 nums1 是较短的数组，这样可以减少搜索范围
  • 计算两个数组的总长度，确定中位数的位置

B. 二分查找过程

  • 在较短的数组 nums1 中寻找分割线位置 i
  • 根据 i 计算 nums2 中的分割线位置 j
  • 比较分割线两侧的元素大小关系

C. 边界处理

  • 使用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 处理边界情况
  • 分别处理总长度为奇数和偶数的情况

🎯 易错点剖析 ​

  1. 数组长度处理

    • 必须确保在较短的数组上进行二分查找
    • 正确处理奇偶数长度的情况

  2. 边界条件

    • 分割线在数组边缘时的处理
    • 两个数组长度差距较大时的情况

  3. 二分查找的条件

    • 正确判断分割线是否合适
    • 准确调整搜索范围

💡 举一反三 ​

这道题的思路可以扩展到其他场景：

  1. 找第k小的数

    • 可以用类似的二分思想

  2. 合并有序数组

    • 理解分割线的概念有助于优化合并过程

  3. 数据流的中位数

    • 类似的思想可以应用到动态数据中

🎨 图解算法 ​

为了更好地理解这个算法，让我们通过可视化来看看它是如何工作的：

svg
<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>
  
  <!-- 第一个数组 -->
  <g transform="translate(50,100)">
    <text x="0" y="-20" font-size="16" fill="#1976d2">nums1:</text>
    <rect width="500" height="50" fill="none" stroke="#1976d2" stroke-width="2"/>
    
    <!-- 数组元素 -->
    <g font-size="14">
      <text x="50" y="30" text-anchor="middle">1</text>
      <text x="150" y="30" text-anchor="middle">3</text>
      <text x="250" y="30" text-anchor="middle">5</text>
      <text x="350" y="30" text-anchor="middle">7</text>
      <text x="450" y="30" text-anchor="middle">9</text>
    </g>
    
    <!-- 分割线 -->
    <line x1="200" y1="0" x2="200" y2="50" stroke="#e91e63" stroke-width="2" stroke-dasharray="5,5"/>
    <text x="200" y="-10" text-anchor="middle" fill="#e91e63">分割线1</text>
  </g>
  
  <!-- 第二个数组 -->
  <g transform="translate(50,200)">
    <text x="0" y="-20" font-size="16" fill="#388e3c">nums2:</text>
    <rect width="500" height="50" fill="none" stroke="#388e3c" stroke-width="2"/>
    
    <!-- 数组元素 -->
    <g font-size="14">
      <text x="50" y="30" text-anchor="middle">2</text>
      <text x="150" y="30" text-anchor="middle">4</text>
      <text x="250" y="30" text-anchor="middle">6</text>
      <text x="350" y="30" text-anchor="middle">8</text>
      <text x="450" y="30" text-anchor="middle">10</text>
    </g>
    
    <!-- 分割线 -->
    <line x1="300" y1="0" x2="300" y2="50" stroke="#e91e63" stroke-width="2" stroke-dasharray="5,5"/>
    <text x="300" y="-10" text-anchor="middle" fill="#e91e63">分割线2</text>
  </g>
  
  <!-- 说明文字 -->
  <g transform="translate(50,300)">
    <text x="0" y="20" font-size="14">左半部分最大值: max(3,6)</text>
    <text x="0" y="40" font-size="14">右半部分最小值: min(5,8)</text>
    <text x="0" y="60" font-size="14">中位数 = (6 + 5) / 2 = 5.5</text>
  </g>
  
  <!-- 箭头 -->
  <defs>
    <marker id="arrowhead" markerWidth="10" markerHeight="7" 
    refX="9" refY="3.5" orient="auto">
      <polygon points="0 0, 10 3.5, 0 7" fill="#666"/>
    </marker>
  </defs>
</svg>

🌟 面试技巧 ​

  1. 思路表达

    • 先说明暴力解法的局限
    • 解释为什么需要用二分查找
    • 清晰描述如何找到分割线

  2. 复杂度分析

    • 解释为什么时间复杂度是 O(log(min(m,n)))
    • 说明空间复杂度是 O(1)

  3. 代码优化

    • 展示对边界情况的处理
    • 说明如何使代码更简洁高效

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #二分查找 #数组

这道题是 LeetCode 难度最高的题目之一，但通过我们的详细讲解，相信大家已经理解了它的核心思想。记住，解决复杂问题的关键在于：将大问题拆分成小问题，找到突破口，然后逐步优化解决方案。如果你对这个题目还有任何疑问，欢迎在评论区讨论！