示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 开源仓库中 LeetCode 4「寻找两个正序数组的中位数」题解中文版为骨架展开系统讲解如何在两个已排序数组中用O(log(mn))复杂度求出中位数。读完本文你将掌握把中位数问题转化为求第 k 小元素的核心思想、分治递归的完整推导与边界处理技巧并对照 Python、Java、C、Go、TypeScript、JavaScript、C#、PHP、Nim、C 十种语言的仓库实现逐一验证。题目描述与约束给定两个大小分别为m和n的正序从小到大数组nums1和nums2找出并返回这两个正序数组的中位数且算法的时间复杂度必须为O(log (mn))。示例 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 mnums2.length n长度范围0 m 10000 n 1000总长范围1 m n 2000元素范围-10^6 nums1[i], nums2[i] 10^6注意m、n都可以为 0但m n 1即至少有一个数组非空。思路分析为什么不能先合并再取中位数最直观的做法是把两个有序数组合并成一个有序数组再直接读取中间位置元素时间复杂度为O(mn)。在m, n 10^3的数据规模下它能通过但题目明确要求O(log (mn))因此线性扫描O(mn)不满足要求必须换用二分查找的思路。关键在于两点观察中位数只关心合并后正中间的一两个位置。比中位数更小的那些元素我们只需要知道它们有多少个而不必真正把它们逐一列出来两个数组都是有序的。因此可以比较两个数组各自第⌊k/2⌋个数据此判断其中某一侧的前一半元素不可能是第k小从而一次性排除一半候选。基于以上观察我们不去构造合并数组而是在两个数组的剩余区间上直接求第 k 小元素。这正是 README_EN.md 中分治Divide and Conquer方法的核心思想。把中位数统一为求第 k 小中位数与奇偶长度的关系若m n为奇数中位数就是第⌊(mn1)/2⌋个数若m n为偶数中位数是第⌊(mn1)/2⌋和第⌊(mn2)/2⌋个数的平均数。事实上可以统一处理无论奇偶中位数都是第⌊(mn1)/2⌋个数与第⌊(mn2)/2⌋个数的平均值。当总长为奇数时例如mn3⌊4/2⌋ 2与⌊5/2⌋ 2指向同一个位置两者相同取平均自然得到该元素本身。因此我们设计函数f(i, j, k)表示在数组nums1的区间[i, m)与数组nums2的区间[j, n)中求第k小的数。中位数的答案即为(f(0, 0, ⌊(mn1)/2⌋) f(0, 0, ⌊(mn2)/2⌋)) / 2核心算法分治求第 k 小f(i, j, k)函数f(i, j, k)的实现逻辑如下递归终止条件三条若i m说明nums1的区间[i, m)已空直接返回nums2[j k - 1]若j n说明nums2的区间[j, n)已空直接返回nums1[i k - 1]若k 1要找的就是第一个数返回min(nums1[i], nums2[j])。一般步骤二分排除令p ⌊k/2⌋分别在两个数组中取第p个数记为x nums1[i p - 1]、y nums2[j p - 1]如果某个数组不足p个元素则将该侧的第p个数视为∞——这样比较时它永远偏大从而只会从另一侧排除元素保证算法不越界且不误删比较x与y若x y说明nums1的第p个数不可能是第k小的数因为它前面最多只有p-1 p-1个比它小的候选不足以排到第k位于是排除nums1的区间[i, i p)递归调用f(i p, j, k - p)若x y同理排除nums2的区间[j, j p)递归调用f(i, j p, k - p)。每次递归都会把k大约减半排除掉⌊k/2⌋个候选元素因此整体时间复杂度为O(log(mn))递归深度为O(log(mn))空间复杂度递归栈也为O(log(mn))。手工推演示例 2以nums1 [1,2]、nums2 [3,4]为例mn 4需要求k1 ⌊5/2⌋ 2与k2 ⌊6/2⌋ 3两个位置的平均值先求f(0, 0, 2)p 1x nums1[0] 1y nums2[0] 3因x y排除nums1[0]递归f(1, 0, 1)→ 返回min(nums1[1], nums2[0]) min(2, 3) 2再求f(0, 0, 3)p 1同样x 1 y 3递归f(1, 0, 2)p 1x nums1[1] 2y nums2[0] 3x y再排除nums1[1]递归f(2, 0, 1)→ 返回nums2[0 1 - 1] 3最终中位数(2 3) / 2 2.5与题目输出一致。仓库中的十种语言实现在 doocs/leetcode 仓库中本题目录solution/0000-0099/0004.Median of Two Sorted Arrays/下以每语言一个独立文件的方式组织题解代码与文档中展示的实现完全一致可直接运行验证。Python3对应文件Solution.pyclass Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: def f(i: int, j: int, k: int) - int: if i m: return nums2[j k - 1] if j n: return nums1[i k - 1] if k 1: return min(nums1[i], nums2[j]) p k // 2 x nums1[i p - 1] if i p - 1 m else inf y nums2[j p - 1] if j p - 1 n else inf return f(i p, j, k - p) if x y else f(i, j p, k - p) m, n len(nums1), len(nums2) a f(0, 0, (m n 1) // 2) b f(0, 0, (m n 2) // 2) return (a b) / 2Python 版本直接用inf充当越界哨兵当某一侧取不到第p个数时该侧被视为正无穷比较后只会排除另一侧的元素。Java对应文件Solution.javaclass Solution { private int m; private int n; private int[] nums1; private int[] nums2; public double findMedianSortedArrays(int[] nums1, int[] nums2) { m nums1.length; n nums2.length; this.nums1 nums1; this.nums2 nums2; int a f(0, 0, (m n 1) / 2); int b f(0, 0, (m n 2) / 2); return (a b) / 2.0; } private int f(int i, int j, int k) { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.min(nums1[i], nums2[j]); } int p k / 2; int x i p - 1 m ? nums1[i p - 1] : 1 30; int y j p - 1 n ? nums2[j p - 1] : 1 30; return x y ? f(i p, j, k - p) : f(i, j p, k - p); } }Java 用1 30约 10.7 亿作为哨兵。因为约束中元素最大为10^6任何远超该上限的整数都可以安全充当∞。C对应文件Solution.cppclass Solution { public: double findMedianSortedArrays(vectorint nums1, vectorint nums2) { int m nums1.size(), n nums2.size(); functionint(int, int, int) f { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return min(nums1[i], nums2[j]); } int p k / 2; int x i p - 1 m ? nums1[i p - 1] : 1 30; int y j p - 1 n ? nums2[j p - 1] : 1 30; return x y ? f(i p, j, k - p) : f(i, j p, k - p); }; int a f(0, 0, (m n 1) / 2); int b f(0, 0, (m n 2) / 2); return (a b) / 2.0; } };C 版本通过std::function定义递归 lambda闭包捕获m、n、nums1、nums2实现思路与 Java 完全一致。Go对应文件Solution.gofunc findMedianSortedArrays(nums1 []int, nums2 []int) float64 { m, n : len(nums1), len(nums2) var f func(i, j, k int) int f func(i, j, k int) int { if i m { return nums2[jk-1] } if j n { return nums1[ik-1] } if k 1 { return min(nums1[i], nums2[j]) } p : k / 2 x, y : 130, 130 if ni : i p - 1; ni m { x nums1[ni] } if nj : j p - 1; nj n { y nums2[nj] } if x y { return f(ip, j, k-p) } return f(i, jp, k-p) } a, b : f(0, 0, (mn1)/2), f(0, 0, (mn2)/2) return float64(ab) / 2.0 }Go 版本使用先声明再赋值的递归闭包写法并将越界时的x、y直接初始化为130再按边界条件覆盖为真实元素值。TypeScript对应文件Solution.tsfunction findMedianSortedArrays(nums1: number[], nums2: number[]): number { const m nums1.length; const n nums2.length; const f (i: number, j: number, k: number): number { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.min(nums1[i], nums2[j]); } const p Math.floor(k / 2); const x i p - 1 m ? nums1[i p - 1] : 1 30; const y j p - 1 n ? nums2[j p - 1] : 1 30; return x y ? f(i p, j, k - p) : f(i, j p, k - p); }; const a f(0, 0, Math.floor((m n 1) / 2)); const b f(0, 0, Math.floor((m n 2) / 2)); return (a b) / 2; }注意 TypeScript/JavaScript 中的k / 2可能产生小数因此用Math.floor(k / 2)显式取整与整数除法语义保持一致。JavaScript对应文件Solution.js/** * param {number[]} nums1 * param {number[]} nums2 * return {number} */ var findMedianSortedArrays function (nums1, nums2) { const m nums1.length; const n nums2.length; const f (i, j, k) { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.min(nums1[i], nums2[j]); } const p Math.floor(k / 2); const x i p - 1 m ? nums1[i p - 1] : 1 30; const y j p - 1 n ? nums2[j p - 1] : 1 30; return x y ? f(i p, j, k - p) : f(i, j p, k - p); }; const a f(0, 0, Math.floor((m n 1) / 2)); const b f(0, 0, Math.floor((m n 2) / 2)); return (a b) / 2; };C#对应文件Solution.cspublic class Solution { private int m; private int n; private int[] nums1; private int[] nums2; public double FindMedianSortedArrays(int[] nums1, int[] nums2) { m nums1.Length; n nums2.Length; this.nums1 nums1; this.nums2 nums2; int a f(0, 0, (m n 1) / 2); int b f(0, 0, (m n 2) / 2); return (a b) / 2.0; } private int f(int i, int j, int k) { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.Min(nums1[i], nums2[j]); } int p k / 2; int x i p - 1 m ? nums1[i p - 1] : 1 30; int y j p - 1 n ? nums2[j p - 1] : 1 30; return x y ? f(i p, j, k - p) : f(i, j p, k - p); } }PHP对应文件Solution.phpclass Solution { /** * param int[] $nums1 * param int[] $nums2 * return float */ function findMedianSortedArrays($nums1, $nums2) { $m count($nums1); $n count($nums2); $a $this-f($nums1, $nums2, $m, $n, 0, 0, intdiv($m $n 1, 2)); $b $this-f($nums1, $nums2, $m, $n, 0, 0, intdiv($m $n 2, 2)); return ($a $b) / 2; } private function f($nums1, $nums2, $m, $n, $i, $j, $k) { if ($i $m) { return $nums2[$j $k - 1]; } if ($j $n) { return $nums1[$i $k - 1]; } if ($k 1) { return min($nums1[$i], $nums2[$j]); } $p intdiv($k, 2); $x $i $p - 1 $m ? $nums1[$i $p - 1] : 1 30; $y $j $p - 1 $n ? $nums2[$j $p - 1] : 1 30; return $x $y ? $this-f($nums1, $nums2, $m, $n, $i $p, $j, $k - $p) : $this-f($nums1, $nums2, $m, $n, $i, $j $p, $k - $p); } }PHP 使用intdiv()进行整除并把数组、长度与下标作为参数显式传入递归方法。Nim对应文件Solution.nimproc medianOfTwoSortedArrays(nums1: seq[int], nums2: seq[int]): float let m nums1.len n nums2.len proc f(i, j, k: int): int if i m: return nums2[j k - 1] if j n: return nums1[i k - 1] if k 1: return min(nums1[i], nums2[j]) let p k div 2 let x if i p - 1 m: nums1[i p - 1] else: 1 shl 30 let y if j p - 1 n: nums2[j p - 1] else: 1 shl 30 if x y: result f(i p, j, k - p) else: result f(i, j p, k - p) let a f(0, 0, (m n 1) div 2) b f(0, 0, (m n 2) div 2) result (a b) / 2Nim 使用div整除、shl左移构造哨兵并借助嵌套 proc 实现递归。C对应文件Solution.cint findKth(int* nums1, int m, int i, int* nums2, int n, int j, int k) { if (i m) return nums2[j k - 1]; if (j n) return nums1[i k - 1]; if (k 1) return nums1[i] nums2[j] ? nums1[i] : nums2[j]; int p k / 2; int x (i p - 1 m) ? nums1[i p - 1] : INT_MAX; int y (j p - 1 n) ? nums2[j p - 1] : INT_MAX; if (x y) return findKth(nums1, m, i p, nums2, n, j, k - p); else return findKth(nums1, m, i, nums2, n, j p, k - p); } double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) { int total m n; int a findKth(nums1, m, 0, nums2, n, 0, (total 1) / 2); int b findKth(nums1, m, 0, nums2, n, 0, (total 2) / 2); return (a b) / 2.0; }C 版本将求第 k 小独立成findKth顶层函数越界哨兵使用INT_MAX需引入limits.h语义与其他语言完全一致。边界情况与易错点结合上述实现有几个细节值得特别注意空数组m或n可能为 0。此时第一、第二个终止条件会立即命中例如nums1为空时直接返回nums2[k-1]逻辑天然正确哨兵值的选择当某一侧不足⌊k/2⌋个元素时必须将该侧视为∞。各语言分别用inf、1 30、INT_MAX实现它们的共同前提是元素值上限仅10^6任意大于该上限的值都能安全充当哨兵且比较后只会排除另一侧不会越界访问奇偶统一求⌊(mn1)/2⌋与⌊(mn2)/2⌋两个位置并取平均一套代码同时覆盖奇偶长度无需单独分支整除与浮点在 JavaScript/TypeScript 中k / 2可能得到小数必须用Math.floor取整返回中位数时Java/C/C#/C/Go 需用2.0或float64转换确保浮点除法避免整数截断k 1的兜底递归每轮至少排除一个元素最终必然收敛到k 1或某一侧为空递归必定终止。复杂度与总结时间复杂度O(log(mn))。每轮递归将k减半排除⌊k/2⌋个候选满足题目要求空间复杂度O(log(mn))。来自递归调用的栈深度若改用迭代写法可优化到O(1)辅助空间。本题的核心套路可以抽象为一句可复用的方法论在多个有序序列上求第 k 小可以通过比较各序列第⌊k/2⌋个元素成块丢弃必然不可能是答案的前缀从而把线性扫描加速到对数复杂度。这一技巧同样适用于两个有序数组的第 k 小元素等变体题目。需要说明的是doocs/leetcode 仓库当前为本题收录的正是上述分治求第 k 小解法对应 README_EN.md 的方法一并且将中文文档、英文文档与十种语言的Solution.*文件统一存放在solution/0000-0099/0004.Median of Two Sorted Arrays/目录下。如需本地运行验证可将对应语言的Solution类/函数复制到本地环境执行例如 Python 版本在使用前补充from typing import List即可直接调用findMedianSortedArrays跑通两个示例。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解精讲LeetCode 4 寻找两个正序数组的中位数——O(log(mn)) 二分分治解法doocs/leetcode 题解精讲LeetCode 4 寻找两个正序数组的中位数——O log mn 二分分治解法 本文以 doocs/leetcode示例工程uBlock Origin5 分钟装好免费的广告与跟踪拦截器uBlock Origin5 分钟装好免费的广告与跟踪拦截器 uBlock Origin 是一款免费开源的浏览器扩展它能在广告请求、跟踪脚本和恶意代码加载进网络安全应用安全LeetCode 0004 寻找两个正序数组的中位数从暴力合并到 O(log(min(n,m))) 二分划分含多语言实现LeetCode 0004 寻找两个正序数组的中位数从暴力合并到 O log min n,m 二分划分含多语言实现 导读 本篇围绕 LeetCode 第示例工程上一篇SRWE Profile深度解析把繁琐的窗口调整变成一键还原16:9到21:9配置实战下一篇WinPython-64bit 3.9.10.0 变更历史全解读3.9.8.0 以来的包升级全景与 _History.md 自动生成机制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考