企业官网建设流程全解析

1. 读懂题目比写代码更重要：中位数的隐藏细节

1.1 先别急着敲代码，把“中位数”定义捋清楚

中位数的定义很基础，但放到“两个数组”里就变味了。一组数据从小到大排列之后，如果个数是奇数，中位数就是正中间那个数；如果个数是偶数，则是中间两个数的平均值。

题目把两个数组合并成一个的话，总长度 m+n 的奇偶直接决定最后怎么取值：

• m+n 为奇数时，合并后第(m+n)//2 + 1个元素就是中位数；
• m+n 为偶数时，中位数是第(m+n)//2个元素和第(m+n)//2 + 1个元素的平均值。

这两个下标在后续所有解法里都会反复出现。我第一次做这道题时，就是因为没把这条基础法则写下来，写一半代码就晕了。建议你先拿纸笔把这两个公式写清楚，再动手。

顺便说一个容易忽略的点：这道题说的是“正序数组”，也就是升序数组。这个条件不是白给的，它意味着数组本身已经排序完毕，我们不需要在任何环节做全量排序。很多初学者上来就sorted(nums1 + nums2)，等于把题目给的两个有序条件完全浪费了。

1.2 先写一个最笨的版本：逻辑对，但别急着提交

我在练基础题时有个习惯：先写一个绝对不出错的版本，保证自己理解对题目，再考虑效率。从“合并两个数组，排序，取中位数”入手是最自然的。

def find_median_sorted_arrays(nums1, nums2): merged = sorted(nums1 + nums2) n = len(merged) if n % 2 == 1: return merged[n // 2] else: return (merged[n // 2 - 1] + merged[n // 2]) / 2.0

这个版本的好处是直接，不容易写错。但它的时间复杂度是 O((m+n)log(m+n))，因为sorted()底层是 Timsort，要对合并后的整个数组做一次排序。空间上也是 O(m+n)，因为真把两个数组合起来存了一份。

如果题目没有复杂度要求，这种写法交上去完全能过。但正因为这道题要求的 O(log(m+n))，这个“暴力版”只能作为理解题目的基线，不能作为最终答案。

1.3 暴力版暴露出的两个关键信号

写完暴力版之后，我做了一个操作：打印合并后的完整数组，再对比手算的中位数。别小看这一步，它能帮你确认边界定义是否理解到位。

nums1 = [1, 3] nums2 = [2] # 合并后 [1, 2, 3]，中位数 2 nums3 = [1, 2] nums4 = [3, 4] # 合并后 [1, 2, 3, 4]，中位数 (2+3)/2 = 2.5

跑完这两个用例，我理解了题目的核心矛盾：一方面我们要用到“合并后数组”的中位位置；另一方面，我们其实并不需要把合并后的数组完整生成出来，只需要在扫描过程中跟踪中位位置附近的元素就够了。

这是整道题最重要的思路转折点——很多解法优化的本质，都是在回答一个问题：能不能不生成完整数组，却准确得到中位位置的元素？

2. 双指针合并：手写归并，把空间和常数时间降下来

2.1 两个有序数组的“归并”是什么

既然两个数组已经分别有序，合并它们最经典的方式就是双指针归并。定义两个下标 i、j 分别指向两个数组开头，每次比较nums1[i]和nums2[j]，谁小就把谁放入结果，同时前进对应的指针。这个过程就是归并排序中 merge 那一步。

关键是：我们不需要保留合并后的完整结果，只需要在中位位置停下来。更准确地说，只要扫描到第total // 2 + 1个位置就够了，因为偶数长度时还要用到前一个元素。所以用一个变量prev保存上一次取出的值，用cur保存当前取出的值。

2.2 双指针版的最优实现

def find_median_sorted_arrays(nums1, nums2): m, n = len(nums1), len(nums2) total = m + n prev = cur = 0 i = j = 0 for _ in range(total // 2 + 1): prev = cur if i < m and (j >= n or nums1[i] <= nums2[j]): cur = nums1[i] i += 1 else: cur = nums2[j] j += 1 if total % 2 == 1: return cur return (prev + cur) / 2.0

这段代码有几点值得仔细琢磨：

• if i < m and (j >= n or nums1[i] <= nums2[j])这行把三种情况合并处理了。i < m保证前半部分不会越界；j >= n表示 nums2 已经取完，只能取 nums1 的；nums1[i] <= nums2[j]是常规比较。
• total // 2 + 1这个循环次数在奇数和偶数情况下都够用。奇数时正好取到中位数；偶数时最后一次循环会把第二个中间数赋给cur，前一个存在prev。
• 整个过程只用到了 O(1) 额外空间，时间复杂度是 O(m+n)。

这个版本比起sorted()版本，空间上省了很多，时间上也从 O((m+n)log(m+n)) 降到了 O(m+n)。在基础练习阶段，这已经是一次合格的优化。

2.3 为什么双指针还不是终点

双指针版交上去能通过大多数基础测试，但在原题严格要求 O(log(m+n)) 的情况下依然不达标。原因很直接：两个数组的规模如果都很大，比如各 100 万个元素，O(m+n) 的扫描就是 200 万次操作。这已经比 O(n) 好不少，但题目想要的是只需探测几十次就能定位中位数。

看到 O(log(m+n)) 这个符号，第一反应应该是二分查找。因为只有二分类算法，才能在对数时间内把搜索范围不断减半。

这也是我学这道题的最大收获：读题时复杂度要求不是摆设，它是出题人给你的解题方向提示。如果题目要求 O(m+n)，双指针就是正解；要求 O(log(m+n))，就必须走二分。

3. 二分核心思路：把中位数问题转化成“求第 k 小元素”

3.1 转化：中位数本质上是合并后数组的第 k 小元素

设总长度total = m + n。如果total是奇数，中位数是第total//2 + 1小的元素；如果是偶数，中位数是第total//2小和第total//2 + 1小的平均值。

于是问题变成：给定两个有序数组，如何快速找到合并后的第 k 小元素。这里的 k 就是上面算出来的一个或两个下标。

这个转化极其关键，因为它把“中位数”这个具体问题，变成了一个更通用的问题。只要能高效求出第 k 小，奇偶两种情况都能处理。

3.2 二分查找的核心逻辑：一次扔一半

常规二分是在一个数组里折半查找。现在是两个有序数组，怎么折半？

核心想法是这样：两个数组当前各自的起点分别是 i 和 j，我们从 nums1 取k//2个候选元素，从 nums2 也取k//2个候选元素，然后比较两组候选元素中最后一个元素的大小。

举例说明。nums1 的前k//2个元素最后一个比 nums2 的前k//2个元素最后一个小，那么 nums1 的前k//2个元素肯定整体小于合并后的第 k 小元素，可以放心地把这部分丢掉，同时在 k 上减去这部分长度。反之就丢 nums2 的前k//2个。

这样每轮都把搜索范围缩小 k//2，k 本身不断减小，直到变成 1，直接返回两个数组当前起点中较小的那个即可。整体时间复杂度就是 O(log(m+n))。

3.3 迭代法实现：处理边界是这里的关键

直接用递归写很容易理解，但 Python 递归会有调用深度和性能损耗，我选择迭代写法。

def find_median_sorted_arrays(nums1, nums2): def get_kth(nums1, nums2, k): m, n = len(nums1), len(nums2) i = j = 0 while True: 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]) half = k // 2 new_i = min(i + half, m) - 1 new_j = min(j + half, n) - 1 if nums1[new_i] <= nums2[new_j]: k -= new_i - i + 1 i = new_i + 1 else: k -= new_j - j + 1 j = new_j + 1 total = len(nums1) + len(nums2) if total % 2 == 1: return get_kth(nums1, nums2, total // 2 + 1) else: left = get_kth(nums1, nums2, total // 2) right = get_kth(nums1, nums2, total // 2 + 1) return (left + right) / 2.0

3.4 逐一解释这段代码里最容易翻车的四个边界

第一个边界是i == m或j == n，代表一个数组已经取完。此时第 k 小元素一定在另一个数组里，直接通过索引偏移j + k - 1或i + k - 1取出来。

第二个边界是k == 1，此时只需要比较当前两个数组的起点元素，取较小者。

第三个边界是new_i = min(i + half, m) - 1。这里为什么要用min？因为当剩余元素个数不足half时，我们不能真的取half个，只能取到数组末尾，否则下标会越界。用min把取数范围限制在数组有效区间内。

第四个边界是丢弃元素个数要用实际丢弃数量new_i - i + 1，而不是直接用half。因为当某个数组剩余不足half时，实际丢弃的个数小于half，k 的减值也必须跟着变化。

我最初写这段代码时，直接k -= half，导致一个很隐蔽的错误：明明丢掉了 2 个元素，k 却减了 3，后面找的位置就全错了。后来逐步打印每一步的 i、j、k 才发现问题。边界不是靠记住，而是靠推演。

3.5 手推一个完整示例

光看代码容易晕，我建议你像我一样，拿纸笔一步步推一遍。

nums1 = [1, 3, 5] nums2 = [2, 4, 6, 8] total = 7, 中位数是第 4 小元素

第一轮：i=0，j=0，k=4，half=2。new_i = 1，new_j = 1，比较 nums1[1]=3 和 nums2[1]=4，3 <= 4，丢掉 nums1 的 [1, 3]，k 变为 2，i=2。

第二轮：i=2，j=0，k=2，half=1。new_i = 2，new_j = 0，比较 nums1[2]=5 和 nums2[0]=2，5 > 2，丢掉 nums2 的 [2]，k 变为 1，j=1。

第三轮：k=1，比较 nums1[2]=5 和 nums2[1]=4，返回 4。

合并后的数组是 [1, 2, 3, 4, 5, 6, 8]，第 4 小的元素确实是 4。这个结果验证了算法正确。

4. 边界条件与测试用例：拿数据把代码打服

4.1 测试用例设计思路

写算法题，代码写完只是开始，测试才是真正逼你思考边界的环节。我针对这道题设计了一组测试用例，每个用例都在打不同边界。

这些用例覆盖了大多数实际测试点。最后两个尤其值得关注：重复值会让人错误地以为要跳过重复元素，实际上不需要，直接按值比较就能保证正确性；负数则可能让某些人下意识加绝对值，其实完全不需要，比较逻辑对正负数的处理是统一的。

4.2 把测试写成一个函数，一键验证

写个简单的测试函数，把多组用例一次性跑完，这是刷题时最值得养成的习惯。

def run_tests(): cases = [ ([], [1], 1), ([2], [], 2), ([1, 2], [3, 4], 2.5), ([1, 3], [2], 2), ([1, 3, 5], [2, 4, 6], 3.5), ([1, 2, 3, 4], [5, 6], 3.5), ([1, 2, 2], [2, 3, 4], 2), ([-5, 1], [-2, 3], -0.5) ] for nums1, nums2, expected in cases: result = find_median_sorted_arrays(nums1, nums2) status = "PASS" if abs(result - expected) < 1e-9 else "FAIL" print(f"{status}: findByMedian({nums1}, {nums2}) = {result}, expected {expected}") run_tests()

跑出来全部 PASS 之后，我才算真正放心。之前在测试阶段暴露出的问题主要有两类：一类是下标算错导致 IndexError，另一类是 k 值更新与实际丢弃数量不一致，导致结果偏大或偏小。

调试这类问题有个小技巧：在get_kth里临时打印 i、j、k、new_i、new_j，手动走一遍对比，能很快定位到是丢弃数量少了还是 k 减多了。

4.3 双指针版和二分版在边界上的差异

同样一组测试用例，双指针版和二分版在边界处理上有个明显差异：双指针版基本不会越界，因为它的循环次数固定为total // 2 + 1，每次迭代都做合法性判断。而二分版因为涉及k//2与数组剩余长度的比较，越界风险集中在min(i + half, m) - 1这个计算上。

如果少了min，二分版在 nums2 很短时会出现下标越界；如果计算 k 时用了half而不是实际丢弃数量，则会出现逻辑错误。这两个问题在双指针版里都不存在，它更新长度时永远通过指针自增完成，天然安全。

这也是我建议初学者先写双指针版再写二分版的原因：先用一个安全的版本建立正确基线，再让二分版在同样的测试用例下逐步逼近它。

5. 实测对比与最终选择：三种解法放在同一张表里看

5.1 复杂度对比

把三种写法放在一起看，优缺点就很明显。

我实际跑下来的感受是：数据量小的时候三种解法几乎无差别，在[1,3]和[2]这种用例上想秒都不太可能。但当数组长度加到几十万级别时，二分解法明显更快，毕竟它只需要几十次比较操作，而双指针可能要遍历几十万个元素。

所以在基础练习阶段，我的建议是：先保证暴力版和双指针版能流畅写出来，再花功夫理解二分版。不要一上来就盯着最优解背代码，那样代码背下来也是散的。

5.2 除了 get_kth，还有一种划分数组的二分写法

如果你在别的题解里看到另一种二分写法，它通常叫“划分数组法”。思路是固定一个分割点 i 在较短的数组中，另一个数组的分割点 j 也随之确定，使得两个数组左半部分长度之和等于右半部分长度之和，然后调整 i 的位置让左半部分的最大值不超过右半部分的最小值。

这个思路更直接作用于中位数定义，但推导过程涉及的数学公式较多，边界也更多。我在练习时是先把 get_kth 吃透，回头再补划分数组法的。如果你的目标是面试，两者最好都了解；如果只是基础练习，get_kth 已经够用。

5.3 把思路链留在注释里，比代码本身更有价值

最后分享一个我自己的做题习惯：每次跑通一道题，我会把思路链写进文件头部注释里，作为复习线索。

# 思路链：中位数定义 -> 第k小问题转化 -> 每轮丢弃k//2个元素 -> 边界处理 # 关键边界：一个数组取完、k==1、剩余元素不足half、k减的是实际丢弃数

这道题我前前后后写过三个版本，从暴力到双指针再到二分，最大的收获不是背会了某个写法，而是意识到：复杂度要求是题目给的最重要的提示，它直接指向你应该用的算法种类。如果你也和我一样在按天刷 Python 基础练习题，这道题值得在第四天这个节点上好好琢磨，它会把“知道二分思想”变成“会用二分思想解决问题”。