做算法题最怕的就是那种“一看答案就懂一上手就废”的题。LeetCode热题100里的寻找两个正序数组的中位数就是非常典型的一道。表面上是求中位数实际上考察的是二分查找的边界控制能力、递归设计能力以及对时间复杂度的敏感度。你要是去面试后端岗位尤其是Java岗位这题被问到的概率相当高而且面试官通常会让你从暴力解法开始一步步追问到最优解。我最早刷这道题的时候第一反应是合并数组排序然后直接取中间值简单省事。但题目要求在O(log (mn))的时间复杂度内完成这就直接把暴力方案否决了。如果你正在准备面试或者刷题卡在这道题上很久这篇内容会很有帮助。我会从最直观的暴力解法讲起逐步过渡到双指针、二分排除法再到真正的O(log(min(m,n)))最优解代码全部用Java写注释尽量详细读完你不仅能AC这道题还能把这一类“第K小元素”的题目打通。1. 内容整体设计与思路拆解1.1 这道题到底在考什么先看题面给定两个大小分别为m和n的正序从小到大数组nums1和nums2要求找出并返回这两个正序数组的中位数。这里有个细节题目并没有说两个数组长度相同也没说哪个更长所以你的解法必须同时处理奇数长度和偶数长度的情况。很多人在这一步就犯迷糊了为什么要单独讨论奇偶因为中位数的定义有两个分支——如果合并后数组长度为奇数中位数就是最中间那个数如果是偶数中位数就是中间两个数的平均值。直接合并数组的做法时间复杂度是O(mn)虽然能过一些测试用例但遇到大数据量会超时。最优解要求O(log(min(mn)))。看到log就应该条件反射想到二分查找这是解题方向的核心线索。1.2 方案选型的思考路径从暴力到最优解其实就是一个逐步优化的过程每一层优化背后都有明确的动机第一层是暴力合并它的优点是直觉、好写、不容易出错适合用来验证思路缺点是时间复杂度和空间复杂度都比较高。第二层是双指针归并它不需要额外开辟新数组节省了空间但时间复杂度仍然是O(mn)。第三层是二分排除法不需要真正归并数组而是通过不断排除不可能是答案的元素来逼近目标时间复杂度降到了O(log(mn))已经满足题目要求了但代码还有优化空间。第四层是分割法这是最优解时间复杂度进一步降到O(log(min(mn)))核心思路是利用较短数组做二分切割通过比较切割点两侧的值来确定正确分割位置。我自己刷题的习惯是先把暴力解写出来跑通之后再去想优化。不要一上来就奔着最优解去因为你对问题本身还没有足够的感知直接看最优解容易看得懂却记不住下次遇到还是不会。2. 基础解法暴力合并与双指针归并2.1 暴力合并最直观的解法暴力合并的思路很简单把两个数组合并成一个新的数组然后根据新数组的长度奇偶求中位数。代码写起来也不难。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length; int n nums2.length; int[] merged new int[m n]; int i 0, j 0, k 0; while (i m j n) { if (nums1[i] nums2[j]) { merged[k] nums1[i]; } else { merged[k] nums2[j]; } } while (i m) { merged[k] nums1[i]; } while (j n) { merged[k] nums2[j]; } int total m n; if (total % 2 1) { return merged[total / 2]; } else { return (merged[total / 2 - 1] merged[total / 2]) / 2.0; } }这段代码就是把归并排序里的merge操作单独拎出来用。时间复杂度O(mn)空间复杂度O(mn)因为开了新数组。这个方案能不能用能用而且你做笔试的时候如果时间紧迫这个方案能保证你拿一部分分数。但它的缺点也很明显空间浪费。其实我们根本不需要完整的合并数组只需要知道中间位置的那个值就够了所以可以优化成只存储值不存储全部数据。2.2 双指针归并省掉额外数组的开销暴力合并浪费了额外的数组空间那能不能边比较边计数等到走到中位数的位置直接返回当然可以。这就是双指针归并法。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length; int n nums2.length; int total m n; int i 0, j 0; int prev 0, curr 0; for (int k 0; k total / 2; k) { prev curr; if (i m (j n || nums1[i] nums2[j])) { curr nums1[i]; } else { curr nums2[j]; } } if (total % 2 1) { return curr; } else { return (prev curr) / 2.0; } }核心思想用两个指针分别指向两个数组的头部每次比较两个指针指向的元素把较小的那个“取走”然后指针后移。这样的话就不需要真正合并完所有元素只要走到中位数所在的位置就可以停了。但这里要注意几个边界情况。第一个是某个数组已经走完了比如i m那说明nums1已经全部被取走剩下的都从nums2取。第二个是j n同理。第三个是循环次数要保证走到中间位置偶数长度时还需要保留前一个值prev方便算平均值。这个解法的空间复杂度降到了O(1)但时间复杂度还是O(mn)。为什么因为最坏情况下你还是可能要遍历一半以上的元素。比如mn10000你要遍历到第10000或者10001个位置才能拿到中位数。还是不够快下一步就必须上二分。3. 二分排除法把时间复杂度降到对数级3.1 第K小元素的视角既然要找中位数那我们可以换一个角度来看在两个有序数组中找中位数本质上就是找第K小的元素。如果合并后的总长度total是奇数中位数就是第total/21小的元素如果total是偶数中位数就是第total/2小和第total/21小两个元素的平均值。这样问题就转化成了——如何快速地在两个有序数组中找到第K小的元素如果还是通过归并的方式一个一个数那就是O(K)的时间复杂度。K的范围最坏情况下接近(mn)/2还是一个大数。所以我们需要一种跳跃式的搜索方法每一步排除掉尽可能多的元素。3.2 二分排除法的核心策略思想其实很朴素每次比较两个数组中第k/2个元素较小的那个它前面的所有元素都不可能是第K小元素可以直接排除掉。为什么这么说假如数组A的长度足够长B的长度也足够长我们比较A[k/2-1]和B[k/2-1]。假设A[k/2-1]更小那A中前k/2个元素都小于等于A[k/2-1]而B中前k/2-1个元素都小于B[k/2-1]加起来最多k-1个元素比A[k/2-1]小。所以A[k/2-1]最多只是第K-1小的元素它绝对不可能是第K小元素A的前k/2个元素全部可以排除。排除之后K需要减去被排除的元素个数然后继续在剩下的数组中找新的第K小元素。这样每一轮都大约排除k/2个元素整体复杂度就是O(log(mn))。3.3 Java实现与边界控制实现了这个思路代码难点反而在边界处理上。尤其是当某个数组长度不足k/2时我们只能取它的全部长度来比较。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total nums1.length nums2.length; if (total % 2 1) { return getKthElement(nums1, nums2, total / 2 1); } else { return (getKthElement(nums1, nums2, total / 2) getKthElement(nums1, nums2, total / 2 1)) / 2.0; } } private int getKthElement(int[] nums1, int[] nums2, int k) { int m nums1.length; int n nums2.length; int i 0, j 0; while (true) { // 边界情况有一个数组全部被排除了 if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } // 只找第1小的元素直接比较两个数组当前的最小值 if (k 1) { return Math.min(nums1[i], nums2[j]); } // 取 k/2 个元素但要注意数组剩余长度可能不足 int half k / 2; int newI Math.min(i half, m) - 1; int newJ Math.min(j half, n) - 1; if (nums1[newI] nums2[newJ]) { // 排除 nums1 前半段 k - (newI - i 1); i newI 1; } else { // 排除 nums2 前半段 k - (newJ - j 1); j newJ 1; } } }我来说几个关键边界点当某个数组已经被排除完i m第K小元素一定在另一个数组的剩余部分中位置是剩余数组起点加上k-1的偏移量。当k 1时说明只要找最小的那个元素直接比较两个数组当前指针位置的值取较小的返回这其实也等价于min(nums1[i], nums2[j])。取newI的时候一定要用Math.min(i half, m) - 1防止数组越界。这是最容易写错的地方很多人一上来就写i half结果在数组长度不够的时候直接越界。nums1[newI] nums2[newJ]这个判断里小于等于和小于在大部分情况下结果一样但为了稳定性建议取等号时排除第一个数组的元素这样可以减少后续比较次数。这个解法的时间复杂度是O(log(mn))空间复杂度是O(1)。到这里其实已经符合LeetCode对这道题的时间约束了。但还有更优的解法它利用了两个数组中较短的那个数组做二分时间复杂度降到了O(log(min(m,n)))。面试的时候你如果能把这个也讲出来那基本就是满分答案。4. 最优解分割法深入解析4.1 为什么要用较短数组做二分上面说的二分排除法虽然已经是对数级复杂度但它的对数底数是mn。分割法的思路不一样我们不做排除而是直接用二分查找的方式在较短的数组中寻找一个合适的分割点使得左右两侧元素数量相等且满足有序性。为什么选较短的数组因为二分的次数取决于数组长度较短的数组长度小二分次数就少。时间复杂度从O(log(mn))变成O(log(min(mn)))在m和n相差悬殊的时候差距是相当明显的。比如一个数组长度是100万另一个长度是10O(log(1000010))大约是20次迭代而O(log(10))只有3到4次迭代性能提升肉眼可见。4.2 分割法的核心逻辑先把两个数组分别叫作A和B长度分别为m和n。假设m n确保A是较短的数组。我们在A中选取一个分割点i范围是0到m。分割点i的含义是A的左边部分有i个元素A的右边部分有m-i个元素。同理在B中我们需要一个对应的分割点j使得左右两侧总数相等或者说满足以下关系当总长度为偶数时左边元素总数等于总长度的一半也就是ij (mn)/2当总长度为奇数时左边元素总数等于(total1)/2也就是ij (total1)/2。所以可以得到j (mn1)/2 - i。有了i和j之后我们就能得到四个关键值A[i-1]和A[i]B[j-1]和B[j]。其中A[i-1]是A的左半部分最大值B[j-1]是B的左半部分最大值A[i]是A的右半部分最小值B[j]是B的右半部分最小值。如果此时满足两个条件第一个是A[i-1] B[j]也就是说A的左半部分最大值不超过B的右半部分最小值那么就不会出现交错的情况。第二个是B[j-1] A[i]同理B的左半部分最大值不超过A的右半部分最小值。那我们就找到了一个合法的分割点。此时左半部分的最大值就是max(A[i-1], B[j-1])右半部分的最小值就是min(A[i], B[j])。如果总长度是奇数中位数就是左半部分的最大值如果是偶数中位数就是左半部分最大值和右半部分最小值的平均值。如果A[i-1] B[j]说明A的左半部分太大了i应该往左移也就是缩小i。如果B[j-1] A[i]说明B的左半部分太大了j应该往左移反过来也就是i往右移。这就是二分的依据。4.3 Java最优解代码实现这里我直接给出一个完整实现并且在注释里写清楚每一步的判断逻辑。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; int totalLeft (m n 1) / 2; // 左半部分需要的元素总数 int left 0, right m; while (left right) { int i left (right - left 1) / 2; // 注意是向上取整 int j totalLeft - i; if (nums1[i - 1] nums2[j]) { // i 太大需要左移 right i - 1; } else { // i 还可以继续增大 left i; } } int i left; int j totalLeft - i; // 处理边界i0 或 im 时对应位置没有值 int nums1LeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1RightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int nums2LeftMax (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2RightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if ((m n) % 2 1) { return Math.max(nums1LeftMax, nums2LeftMax); } else { return (Math.max(nums1LeftMax, nums2LeftMax) Math.min(nums1RightMin, nums2RightMin)) / 2.0; } }这段代码是整个题解的关键也是面试最常考的版本。我建议你理解之后不要死记硬背而是把分割条件的推导过程写一遍这样才能真正变成自己的东西。4.4 为什么left mid时要向上取整这是一个非常细微但极度容易踩坑的点。在二分分割法的循环里我们用了left (right - left 1) / 2而不是left (right - left) / 2。为什么因为当我们判断nums1[i-1] nums2[j]时要把右边界收缩到right i - 1但判断不成立时要让left i。这种情况下如果mid的计算是向下取整可能会在某个时刻出现left和right相邻且mid恒等于left的情况比如left2, right3时向下取整的mid是2如果此时判断需要执行left mid那left还是2永远无法前进导致死循环。而向上取整可以保证在left和right相邻时mid会等于right这样left mid就能前进到right循环必定会收敛。这是二分查找里非常经典的一个细节掌握了这个细节很多二分的变种题都能轻松应对。5. 时间复杂度的完整对比把四种解法放在一起对比思路就非常清晰了。解法时间复杂度空间复杂度优点缺点暴力合并O(mn)O(mn)思路简单不易出错空间浪费时间不合格双指针归并O(mn)O(1)无需额外空间时间不合格大数据量超时二分排除法第K小O(log(mn))O(1)满足题目时间复杂度要求代码边界较多逻辑稍复杂分割法最优解O(log(min(mn)))O(1)最优性能面试加分项理解成本高边界细节多我曾经在一次代码评审里看到有人把暴力合并的方案提交上去理由是“功能正确”。这确实没错但算法题也好工作场景也罢我们评估代码不能只看“能跑”还要看它在极限条件下的表现。如果是两个长度接近100万的有序数组暴力合并就会创建一个长度200万的临时数组既要花内存又要花时间这在真实业务里是不可接受的。6. 常见问题与排查技巧实录6.1 边界条件总是出错怎么办边界条件出错最常见的就是数组为空、i等于0、i等于m这三种情况。数组为空好处理函数入口处加一个判断如果nums1为空直接去nums2里找中位数如果nums2为空同理。i等于0意味着A的左半部分没有元素那么A[i-1]不存在我们需要把它定义为负无穷也就是Integer.MIN_VALUE这样才能保证在取左半部分最大值时不会干扰B[j-1]。i等于m同理A的右半部分没有元素A[i]要定义为正无穷即Integer.MAX_VALUE。我自己的排查经验是在代码里加上这些边界判断之后再拿几个典型用例跑一下比如nums1为空、nums2只有一个元素、两个数组长度相同、两个数组完全不同区间等情况。这些用例覆盖了绝大部分容易出错的分支。6.2 死循环问题如何定位分割法里如果使用向下取整的mid计算方式很容易出现死循环。这个问题的症状是程序卡住不退出或者线程迟迟不结束。排查的方式就是在while循环里临时打印left、right、i、j的值观察循环是否在某个状态反复横跳。我见过不少人在面试时写这道题当场就卡在死循环里越紧张越找不到问题。这里直接给一个固定套路只要你的二分是在“找左边界”且满足条件时执行left midmid就一定要向上取整。只要你的二分是标准写法满足条件时执行right midmid就可以向下取整。牢记这个结论能规避九成以上的二分死循环问题。6.3 关于数值溢出的隐患在计算两个整数平均值时很多新手会直接写(leftMax rightMin) / 2。如果leftMax和rightMin都是很大的正数加法可能溢出。虽然这道题里的元素取值范围是正负10的6次方加起来不会超过int范围但作为好习惯刷题时应该直接用(leftMax rightMin) / 2.0如果是更大范围的数值更安全的写法是leftMax / 2.0 rightMin / 2.0。同理计算totalLeft的时候(m n 1) / 2在m和n很大的时候也可能溢出更稳妥的写法是m / 2 n / 2 (m % 2 n % 2) / 2不过这道题不会触发这个极限你心里有数就行。7. 面试场景下的作答策略这道题在面试里出现的频率非常高而且面试官基本都是层层递进式提问很少让你一口气写最优解。合理的作答节奏是这样的先别急着动手整理思路然后直接说“这道题我首先想到的是合并数组后取中位数时间复杂度O(mn)空间复杂度O(mn)。但这不符合要求我们可以优化成双指针归并把空间复杂度降到O(1)时间还是O(mn)。再进一步可以用二分查找的思路把它转化成找第K小的元素这样时间复杂度是O(log(mn))。如果要用更优的解法可以利用分割法在较短的数组上二分做到O(log(min(mn)))。”说完这层递进面试官基本就知道你吃透了。接下来你再选择其中一个实现去写。多数情况下面试官会要求你直接写最优解所以分割法的代码一定得手写熟练。另外一个技巧是代码写完不要直接交主动走一遍测试用例。比如nums1 [1,3]nums2 [2]你手动模拟一下i和j的变化过程既能检查边界也能让面试官看到你的调试能力。这比你口头说“我觉得没问题”要有说服力得多。8. 写在最后分割法本质上是在两个有序数组之间人为构造一个“左侧整体小于右侧整体”的切分线这条切分线在不同数组里的位置是关联的。理解了这个关联性你不但能解决这道题还能迁移到很多类似的场景中比如求两个有序数组的第K小值、求两个有序数组的交集、合并K个有序链表等。我个人刷题的经验是这道题值得反复刷三遍。第一遍只求看懂第二遍合上答案自己写第三遍隔一两周再回来写一次确保不是短期记忆。第三遍的时候你会发现之前经常出错的边界条件已经变成了肌肉记忆这就说明你真的掌握了。刷题最重要的不是你刷了多少道而是每一道题你有没有把最优解和推导过程吃透。遇到好的题宁可用三遍的时间去消化也不要走马观花地刷十道。这只是题海战术里的一个锚点把这类核心题掌握好比盲目追求刷题数量要有用得多。