LeetCode-Go 题解：0004.Median of Two Sorted Arrays 二分切分求双有序数组中位数

LeetCode-Go 题解0004.Median of Two Sorted Arrays 二分切分求双有序数组中位数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题LeetCode 4. Median of Two Sorted Arrays要求在两个已排序数组中找到合并后数组的中位数且整体时间复杂度必须为 O(log(mn))。本文以 LeetCode-Go 仓库中该题的中英文题解文档为骨架结合 源码实现 与 单元测试 逐行拆解其核心思路如何把「求中位数」转化为「在较短数组上二分切分位置」以及奇数/偶数长度下如何取左中值与右中值。读完本文你将掌握一套可迁移的二分切分Binary Search on Partition模板理解其边界处理细节并能直接运行仓库测试用例验证结论。题目回顾题目原文见 题解文档核心约束如下给定两个大小分别为 m 和 n 的已排序数组nums1与nums2找出这两个数组合并后有序数组的中位数时间复杂度要求O(log(mn))可以假设nums1与nums2不会同时为空。示例一nums1 [1, 3] nums2 [2] 中位数 2.0示例二nums1 [1, 2] nums2 [3, 4] 中位数 (2 3) / 2 2.5为什么不能直接合并O(mn) 不符合题意最直观的想法是把两个数组合并成有序数组后直接取中位数。但合并两个有序数组本身是 O(mn) 的操作不满足题目要求的 O(log(mn))。看到对数级复杂度自然联想到二分搜索。关键洞察在于两个数组的总长度mn已知因此中位数在最终合并数组中的位置也是确定的第(mn1)/2个1-based只需要在一个数组上二分切分位置另一个数组的切分位置即可由总数减出为了把时间复杂度降到最低应当二分搜索两个数组中较短的那个这是 O(log(min(m,n))) 的来源也严格满足 O(log(mn))。这一推理过程完整记录在 题解文档的 Solution Ideas 一节仓库的 源码实现 第一步就体现了这一策略若len(nums1) len(nums2)则交换两数组递归调用保证nums1恒为较短者。二分切分法核心原理1. 用一条切分线把两个数组切成左右两半对较短数组nums1二分出一个切分点midA则nums1: ……………… nums1[midA-1] | nums1[midA] …………………… nums2: ……………… nums2[midB-1] | nums2[midB] ……………………其中竖线|即切分线左侧包含nums1[0..midA-1]与nums2[0..midB-1]右侧包含nums1[midA..]与nums2[midB..]。切分线两侧的元素数必须满足中位数的位置约束即左右两侧元素个数相等或左侧比右侧多一个。由于两个数组总长度已知中间位置k (len(nums1)len(nums2)1) 1向上取整的一半保证左侧元素数 ≥ 右侧因此一旦确定了midAmidB k - midA就被唯一确定。2. 切分线满足中位数条件的判定切分线何时是「合法」的即线左边的所有数都小于等于线右边的所有数形式化为nums1[midA-1] ≤ nums2[midB] nums2[midB-1] ≤ nums1[midA]若该条件不满足则需要调整切分线位置调整方向有两种若nums1[midA] nums2[midB-1]说明midA这条线划分出来的左侧元素整体偏小切分线应当右移low midA 1若nums1[midA-1] nums2[midB]说明midA这条线划分出来的左侧元素整体偏大切分线应当左移high midA - 1。经过若干次二分调整总能找到满足条件的切分线。这正是二分搜索在有序数组上收敛性的体现越界或不等价关系会在一次二分中把搜索区间缩小一半。3. 找到切分线后如何取中位数假设已找到合法切分线数组 1切分线两侧下标为midA - 1与midA数组 2切分线两侧下标为midB - 1与midB。奇数总长度中位数就是左侧的最大值即max(nums1[midA-1], nums2[midB-1])偶数总长度中间两个数依次为左侧最大值与右侧最小值即max(nums1[midA-1], nums2[midB-1])和min(nums1[midA], nums2[midB])中位数为二者平均值。原文档在此处配有一张切分示意图片原图存放于文档作者的外部图床仓库内未收录故本文以文字与代码注释复现同一示意图。源码逐行拆解仓库中的 核心实现 完整代码如下func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { // 假设 nums1 的长度小 if len(nums1) len(nums2) { return findMedianSortedArrays(nums2, nums1) } low, high, k, nums1Mid, nums2Mid : 0, len(nums1), (len(nums1)len(nums2)1)1, 0, 0 for low high { // nums1: ……………… nums1[nums1Mid-1] | nums1[nums1Mid] …………………… // nums2: ……………… nums2[nums2Mid-1] | nums2[nums2Mid] …………………… nums1Mid low (high-low)1 // 分界限右侧是 mid分界线左侧是 mid - 1 nums2Mid k - nums1Mid if nums1Mid 0 nums1[nums1Mid-1] nums2[nums2Mid] { // nums1 中的分界线划多了要向左边移动 high nums1Mid - 1 } else if nums1Mid ! len(nums1) nums1[nums1Mid] nums2[nums2Mid-1] { // nums1 中的分界线划少了要向右边移动 low nums1Mid 1 } else { // 找到合适的划分了需要输出最终结果了 // 分为奇数偶数 2 种情况 break } } midLeft, midRight : 0, 0 if nums1Mid 0 { midLeft nums2[nums2Mid-1] } else if nums2Mid 0 { midLeft nums1[nums1Mid-1] } else { midLeft max(nums1[nums1Mid-1], nums2[nums2Mid-1]) } if (len(nums1)len(nums2))1 1 { return float64(midLeft) } if nums1Mid len(nums1) { midRight nums2[nums2Mid] } else if nums2Mid len(nums2) { midRight nums1[nums1Mid] } else { midRight min(nums1[nums1Mid], nums2[nums2Mid]) } return float64(midLeftmidRight) / 2 }关键变量与二分框架变量含义low/high在较短数组nums1上二分搜索的左右边界初始为0与len(nums1)k最终合并数组中中位数的「左侧元素总数」(mn1) 1保证奇数长度时左侧比右侧多 1nums1Mid切分线在nums1上的位置右侧起始下标为mid左侧最后一个下标为mid - 1nums2Mid切分线在nums2上的位置由k - nums1Mid推导得出midLeft/midRight最终合并数组中间位置左侧与次中间位置右侧的值注意nums1Mid low (high-low)1的写法先算差值再右移一位等效于(lowhigh)/2但可避免整型溢出是二分模板中的推荐写法。边界条件的四个分支midLeft的取值需要处理切分线落在数组边缘的情况nums1Mid 0nums1整体都在切分线右侧左侧最大值只能来自nums2取nums2[nums2Mid-1]nums2Mid 0nums2整体都在切分线右侧左侧最大值只能来自nums1取nums1[nums1Mid-1]其余情况左侧最大值取max(nums1[nums1Mid-1], nums2[nums2Mid-1])。midRight同理有对称的三个分支nums1Mid len(nums1)、nums2Mid len(nums2)、一般情况取min(...)。这四个边界分支是本题最容易写错的地方也正是 单元测试 中用专门用例逐一覆盖的原因详见下文。奇偶长度的收尾总长度为奇数时(mn)1 1直接返回float64(midLeft)即左侧最大值即为中位数总长度为偶数时返回float64(midLeftmidRight)/2即左右两个中间值的平均数。单元测试如何验证每个分支仓库为该题编写了 9 组用例存放在 4. Median of Two Sorted Arrays_test.go每组用例都有明确的覆盖意图输入nums1/nums2期望输出覆盖分支[1,3]/[2]2.0题目示例一奇数长度[1,2]/[3,4]2.5题目示例二偶数长度[1,2,3,4]/[5]3.0nums1更长触发首行 swap 递归[3,4]/[1,2]2.5nums1Mid 0且偶数长度midLeft取nums2[4,5,6]/[1,2,3]3.5nums2Mid 0分支nums1整体在切分线右侧[1,2]/[3,4,5,6]3.5nums1Mid len(nums1)分支midRight取nums2[2,2]/[2,2]2.0元素相等触发max/min中a b非a b路径[1,3,5]/[2,4]3.0奇数总长度[1,4]/[2,3]2.5触发min的a b分支右侧取nums2的较小值测试框架采用表驱动风格para4封装两个输入数组ans4封装期望答案测试循环对每组(para, ans)调用findMedianSortedArrays一旦结果与期望不符即t.Fatalf失败并打印输入与输出。从测试注释可以看出作者刻意覆盖了「短数组在前 / 长数组在前」「切分线落在数组两端」「元素全部相等」等极端场景为二分边界正确性提供了可复现的验证依据。如需在本地运行该测试可执行go test -v ./leetcode/0004.Median-of-Two-Sorted-Arrays/若想生成并查看全仓库覆盖率报告仓库根目录的 gotest.sh 提供了标准做法bash gotest.sh go tool cover -funccoverage.txt | grep findMedianSortedArrays复杂度分析时间复杂度二分搜索仅在较短数组上进行每次迭代将搜索区间减半因此为 O(log(min(m,n)))又因为 min(m,n) ≤ (mn)/2log(min(m,n)) ≤ log(mn)严格满足题目要求的 O(log(mn))空间复杂度除常数个变量low、high、k、nums1Mid、nums2Mid、midLeft、midRight外无额外分配为 O(1)递归 swap 仅发生在首层深度为 1不随输入规模增长。总结本题的标准解法是把「合并求中位数」转化为「在较短有序数组上二分切分位置」用k反推另一数组的切分位置通过两条不等式判定切分线合法性并二分调整最后按奇偶长度取左侧最大值与右侧最小值计算中位数。仓库的 源码实现 结构清晰、边界完备题解文档 给出了从 O(mn) 朴素思路到 O(log(min(m,n))) 二分方案的完整推导路径单元测试 则为每个边界分支提供了可运行验证。掌握「短数组二分 位置反推 奇偶收尾」这一模板后可以平滑迁移到其他「有序结构中求第 k 小」类问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考