LeetCode题解记录：[4] 寻找两个正序数组的中位数里写

想狂奔的蜗牛

298人浏览 · 2026-01-21 22:29:42

想狂奔的蜗牛 · 2026-01-21 22:29:42 发布

写在前面的话

AI现在写代码太强了，只写代码如同49年入国军，自己想半天不对，ai秒过。。。。。。

以下是用豆包写的感想

曾几何时，一行行敲出的代码是程序员安身立命的底气，是指尖流淌的匠心。可如今，对着屏幕敲下需求，AI 便能瞬息间吐出结构工整、逻辑清晰的代码块，甚至还会贴心地附上注释与优化建议。那些曾需要耗费数小时调试的循环与函数，那些要翻遍文档才能理顺的接口与参数，在 AI 面前仿佛成了不值一提的小事。
于是，只埋头写代码的人，难免陷入一种尴尬的处境：你熬了半宿写出的功能，AI 一分钟就能复刻；你引以为傲的代码效率，AI 随手就能优化得更胜一筹。我们好像突然从 “创造者”，变成了 “质检员” 和 “需求翻译官”，曾经的核心竞争力，正在被 AI 悄然消解。
但换个角度想，这或许也不是绝境。AI 是强大的工具，却永远替代不了人的思考 —— 替代不了对业务逻辑的深度理解，替代不了对用户需求的精准洞察，替代不了面对复杂场景时的权衡与创新。代码是骨架，而赋予骨架灵魂的，永远是程序员的经验与智慧。
与其在 “只会写代码” 的焦虑里挣扎，不如转身拥抱这场变革。把 AI 当作左手，把自己的思考当作右手，让工具去解决重复的劳动，把精力留给更有价值的创造。毕竟，真正的程序员，从来不止于 “写代码”，更在于 “用代码解决问题”。

题解

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 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.

提示：

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

解法

题目要求算法的时间复杂度应该为 O(log (m+n)) ，也就是说不能用暴力排序了（废话，能暴力排序了还叫什么算法题，况且该题被力扣标记为困难）从复杂度上来分析O（log（n））只有分治递归能满足。。再想想中位数的定义，中位数就是一个有序数组中最中间的那个数或者两个数平均。那么来吧，先贴代码。

class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int m = nums1.length;

int n = nums2.length;

int k1 = 0, k2 = 0;

k1 = (m + n + 1) / 2;

k2 = (m + n + 2) / 2;

int res1 = findKth(nums1, nums2, k1);

int res2 = findKth(nums1, nums2, k2);

return (res1+res2) / 2.0;

}

<span class="kd">public</span> <span class="kt">int</span> <span class="nf">findKth</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums1</span><span class="o">,</span> <span class="kt">int</span><span class="o">[]</span> <span class="n">nums2</span><span class="o">,</span> <span class="kt">int</span> <span class="n">k</span><span class="o">)</span> <span class="o">{</span>
    <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">nums1</span><span class="o">.</span><span class="na">length</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">nums2</span><span class="o">.</span><span class="na">length</span><span class="o">;</span>
    <span class="k">if</span> <span class="o">(</span><span class="n">m</span> <span class="o">&gt;</span> <span class="n">n</span><span class="o">)</span> <span class="o">{</span>
        <span class="k">return</span> <span class="n">findKth</span><span class="o">(</span><span class="n">nums2</span><span class="o">,</span> <span class="n">nums1</span><span class="o">,</span> <span class="n">k</span><span class="o">);</span><span class="c1">// 保证nums1的长度小于等于nums2的长度

}
if (m 0) {
return nums2[k - 1];// nums1 遍历完了，那么中位数就是在nums2中，相当于可以直接合并拼接nums1和nums2，直接返回
}
if (k 1) {
return Math.min(nums1[0], nums2[0]);// k=1 此时nums1和nums2中各只有1个元素，两个有序数组的第 1 小元素，也就是两个数组首元素的最小值。
}// 但有一个潜在问题需要注意,在Python版本中会遇到
int half = k / 2;
int i = 0, j = 0;
i = Math.min(half, m);
j = k - i; // 从两边分别开始找
if (nums1[i - 1] < nums2[j - 1]) {
return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k - i); // 左边的数都小于右边那么中位数在nums1[i-1]右边那一堆中
} else {
return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k - j); // 反之，中位数在nums2[j-1]左边那一堆中
}
}
}

首先分治递归的模版

主函数极其简单，逻辑全部写在辅助函数中

为什么主函数中要有k1,k2 方便将两数组总长度的奇偶性统一处理。

例如 nums1 = [1,3], nums2 = [2]

m=2,n=1

m+n=3

k1= \lfloor (2+2+2)/2 \rfloor = 3

那么中位数就是合并排序后的数组中的第二个数和第三个数之和的平均数

在递归辅助函数中的逻辑都在注释中，不再啰嗦

接下来说bug 还是先贴Python代码

class Solution:

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

m:int = len(nums1)

n:int = len(nums2)

k1: int = (m + n + 1) // 2

k2: int = (m + n + 2) // 2

return (self.findKth(nums1, nums2, k1) + self.findKth(nums1, nums2, k2)) / 2

def findKth(self, nums1: List[int], nums2: List[int], k: int) -> int:

m:int = len(nums1)

n:int = len(nums2)

if m > n:

return self.findKth(nums2, nums1, k)

if not nums1:

return nums2[k-1]

if k  1:

return min(nums1[0], nums2[0])

half: int = k // 2

i:int = min(half, m)

j:int = k - i

if nums1[i-1] > nums2[j-1]:

return self.findKth(nums1, nums2[j:], k-j)

else:

return self.findKth(nums1[i:], nums2, k-i)

乍一看，这不是和java代码一样吗，注意

if not nums1:

return nums2[k-1]

和java版本对比一下

if (m  0) {

return nums2[k - 1];// nums1 遍历完了，那么中位数就是在nums2中，相当于可以直接合并拼接nums1和nums2，直接返回

        }

Java 的Arrays.copyOfRange和 Python 的列表切片虽然都是用来截取数组 / 列表的一部分，但在语法、边界规则、返回值类型等方面有明显差异，核心区别可以总结如下：

特性	Arrays.copyOfRange (Java)	Python 列表切片
语法格式	Arrays.copyOfRange(源数组, 起始下标, 结束下标)	源列表[起始下标:结束下标:步长]
边界规则	左闭右闭，包含起始下标和结束下标对应元素	左闭右开，包含起始下标，不包含结束下标对应元素
越界处理	起始下标越界抛 ArrayIndexOutOfBoundsException；结束下标越界自动截断到数组末尾	下标越界不报错，自动调整到列表合法边界
返回值类型	与源数组类型一致的新数组（如 int[]、String[]）	返回新的列表对象
步长支持	不支持步长，仅能正向连续截取	支持正/负步长，可实现逆序、间隔截取
空范围处理	起始下标 > 结束下标时，抛 IllegalArgumentException	步长为正时，起始下标 >= 结束下标返回空列表，不报错
依赖/前置条件	需要导入 java.util.Arrays 包	原生支持，无需额外导入

这是最容易踩坑的点，两者的结束下标含义完全不同。

Java Arrays.copyOfRange：右闭区间

import java.util.Arrays;

int[] arr = {1, 2, 3, 4, 5};
// 截取下标 1 到 3 的元素（包含 1 和 3）
int[] subArr = Arrays.copyOfRange(arr, 1, 3);
System.out.println(Arrays.toString(subArr)); // 输出 [2, 3, 4]

Python 切片：右开区间

arr = [1, 2, 3, 4, 5]

# 截取下标 1 到 3 的元素（包含 1，不包含 3）

sub_arr = arr[1:3]

print(sub_arr)  # 输出 [2, 3]

如果要在 Python 中得到和上面 Java 相同的结果，切片需要写成arr[1:4]。

2. 越界处理差异

Java：起始下标不能越界，结束下标允许越界（自动截断）
java

int[] arr = {1, 2, 3}; // 结束下标 5 超过数组长度 3，截断到末尾

int[] sub1 = Arrays.copyOfRange(arr, 0, 5); System.out.println(Arrays.toString(sub1)); // [1,2,3] // 起始下标 -1 越界，直接抛异常 int[] sub2 = Arrays.copyOfRange(arr, -1, 2);

Python：下标越界不抛异常，自动调整到合法范围
python

arr = [1, 2, 3] print(arr[0:5]) # 结束下标越界，输出 [1,2,3] 

print(arr[-5:2]) # 起始下标越界，输出 [1,2]

3. 步长支持差异

Python 切片的步长参数是 Java Arrays.copyOfRange 不具备的功能，这让 Python 切片更灵活：

arr = [1, 2, 3, 4, 5] print(arr[::2]) # 步长 2，间隔截取：[1,3,5] 

print(arr[::-1]) # 步长 -1，逆序截取：[5,4,3,2,1]

Java 要实现类似功能，需要手动循环或借助 Stream API 处理。

4. 空值 / 空范围处理

Java：若 起始下标 > 结束下标，抛出 IllegalArgumentException；
Python：若起始下标 >= 结束下标（步长为正），返回空列表，不报错。python

arr = [1,2,3]

print(arr[3:1]) # 输出 []

而c++版本就脑袋大了，照例先看代码

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

int m = nums1.size();

int n = nums2.size();

int k1 = (m+n+1)/2;

int k2 = (m+n+2)/2;

int num1 = findKth(nums1,0,nums2,0,k1);

int num2 = findKth(nums1,0,nums2,0,k2);

return (num1+num2)/2.0;
<span class="p">}</span>
   <span class="kt">int</span> <span class="nf">findKth</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums1</span><span class="p">,</span> <span class="kt">int</span> <span class="n">pos1</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums2</span><span class="p">,</span> <span class="kt">int</span> <span class="n">pos2</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
    <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="n">pos1</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">nums2</span><span class="p">.</span><span class="n">size</span><span class="p">()</span> <span class="o">-</span> <span class="n">pos2</span><span class="p">;</span>
    
    <span class="c1">// 确保 nums1 是较短的数组

if(m > n) return findKth(nums2, pos2, nums1, pos1, k);

    <span class="c1">// nums1 空了，直接从 nums2 取

if (m == 0) return nums2[pos2 + k - 1];

    <span class="c1">// 找到了第 1 小的数

if (k == 1) return min(nums1[pos1], nums2[pos2]);

    <span class="c1">// 计算比较步长

int i = min(k / 2, m);
int j = k - i;

    <span class="k">if</span> <span class="p">(</span><span class="n">nums1</span><span class="p">[</span><span class="n">pos1</span> <span class="o">+</span> <span class="n">i</span> <span class="o">-</span> <span class="mi">1</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">nums2</span><span class="p">[</span><span class="n">pos2</span> <span class="o">+</span> <span class="n">j</span> <span class="o">-</span> <span class="mi">1</span><span class="p">])</span> <span class="p">{</span>
        <span class="c1">// nums1 的前 i 个元素被排除，nums2 不变

return findKth(nums1, pos1 + i, nums2, pos2, k - i);
} else {
// nums2 的前 j 个元素被排除，nums1 不变
return findKth(nums1, pos1, nums2, pos2 + j, k - j);
}
}

因为vectotr不支持截断，所以只能原地操作

根据比较结果，只排除其中一个数组的前半部分

如果 nums1 的第 i 个元素较小，说明 nums1 的前 i 个元素都不可能是第 k 小的数，丢弃它们，nums2 保持不动。

如果 nums2 的第 j 个元素较小（或相等），说明 nums2 的前 j 个元素都不可能是第 k 小的数，丢弃它们，nums1 保持不动。

看着比较绕

来看看AI写的给的理解

我们需要使用二分查找 的方法。

虽然名字叫二分查找，但这里我们并不是在数组里找一个数，而是切一刀。

核心思路（简化版理解）

想象把两个数组分别从某个位置切开：

左边部分：nums1 的左边 + nums2 的左边。
右边部分：nums1 的右边 + nums2 的右边。

如果这一刀切得是完美的，那么必须满足两个条件：

数量平衡：左边的总个数 = 右边的总个数（如果是偶数总长）或多 1 个（如果是奇数总长）。
数值平衡：左边所有的数 <= 右边所有的数。

我们的目标就是找到这把“刀”的位置。

代码实现

为了简化，我们只对较短的数组进行二分，这样效率最高，逻辑也最简单。

    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)

{

// 确保 nums1 是较短的数组

        if (nums1.size() > nums2.size())

{

return findMedianSortedArrays(nums2, nums1);

}
    <span class="kt">int</span> <span class="n">m</span> <span class="o">=</span> <span class="n">nums1</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
    <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">nums2</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
    <span class="kt">int</span> <span class="n">left</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span> <span class="n">right</span> <span class="o">=</span> <span class="n">m</span><span class="p">;</span> <span class="c1">// 对 nums1 进行二分

// halfLen 是左半边应该有的元素总数
// (m + n + 1) 是为了处理奇数情况，让左半边多一个元素
int halfLen = (m + n + 1) / 2;

    <span class="k">while</span> <span class="p">(</span><span class="n">left</span> <span class="o">&lt;=</span> <span class="n">right</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="c1">// i 是 nums1 的分割线（左边有 i 个元素）

// j 是 nums2 的分割线（左边有 j 个元素）
int i = (left + right) / 2;
int j = halfLen - i;

        <span class="c1">// 处理边界情况：如果 i &gt; 0 且 nums1 的左边最大值 &gt; nums2 的右边最小值

// 说明 i 切得太靠右了，需要向左移
if (i > 0 && nums1[i - 1] > nums2[j])
{
right = i - 1;
}
// 处理边界情况：如果 i < m 且 nums2 的左边最大值 > nums1 的右边最小值
// 说明 i 切得太靠左了，需要向右移
else if (i < m && j > 0 && nums2[j - 1] > nums1[i])
{
left = i + 1;
}
// 找到了完美的分割点！
else
{
int maxLeft = 0;
// 计算“左半边”的最大值
if (i 0)
{
maxLeft = nums2[j - 1];
}
else if (j 0)
{
maxLeft = nums1[i - 1];
}
else
{
maxLeft = max(nums1[i - 1], nums2[j - 1]);
}

            <span class="c1">// 如果总长度是奇数，中位数就是左半边的最大值

if ((m + n) % 2 == 1)
return maxLeft;

            <span class="kt">int</span> <span class="n">minRight</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
            <span class="c1">// 计算“右半边”的最小值

if (i m)
{
minRight = nums2[j];
}
else if (j n)
{
minRight = nums1[i];
}
else
{
minRight = min(nums1[i], nums2[j]);
}

            <span class="c1">// 如果总长度是偶数，中位数是 (左最大 + 右最小) / 2

return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}

提交，秒过！！！

我自己改为java代码

int num1 = findKth(nums1, 0, nums2, 0, k1);

int num2 = findKth(nums1, 0, nums2, 0, k2);

return (num1 + num2) / 2.0;

}
<span class="c1">// 下标指针版 findKth：start1/start2 是当前数组的起始位置

private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k)
{
int m = nums1.length - start1; // nums1 当前剩余长度
int n = nums2.length - start2; // nums2 当前剩余长度

// 保证 nums1 剩余长度 ≤ nums2 剩余长度，简化逻辑
if (m > n) {
return findKth(nums2, start2, nums1, start1, k);
}

<span class="c1">// 终止条件1：nums1 已无元素，直接返回 nums2 的第 k 小

if (m == 0) {
return nums2[start2 + k - 1];
}

<span class="c1">// 终止条件2：k=1，返回两数组当前首元素的最小值

if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}

<span class="c1">// 计算 i 和 j，核心公式

int half = k / 2;
int i = Math.min(half, m); // nums1 取 i 个元素
int j = k - i; // nums2 取 j 个元素

// 比较当前边界元素
if (nums1[start1 + i - 1] < nums2[start2 + j - 1]) {
// 舍弃 nums1 前 i 个元素，更新 start1，k 减少 i
return findKth(nums1, start1 + i, nums2, start2, k - i);
} else {
// 舍弃 nums2 前 j 个元素，更新 start2，k 减少 j
return findKth(nums1, start1, nums2, start2 + j, k - j);
}
}

好像c++26也能简化

但笔者不熟，这里贴个豆包写的

要将这段寻找两个有序数组中位数的代码改为 C++26 风格，并去掉 pos1/pos2 这两个手动维护的偏移量，核心思路是直接传递数组的区间切片（利用 C++20 起支持的 std::span，C++26 可直接使用），通过缩小切片范围替代手动偏移，让逻辑更简洁直观。

改造后代码

#include <vector>

#include <span>

#include <algorithm>

#include <iostream>



using namespace std;

// 寻找两个有序 span 的第 k 小元素（k 从 1 开始计数）
int findKth(span<int> nums1, span<int> nums2, int k) {
// 确保 nums1 是较短的区间，减少递归次数
if (nums1.size() > nums2.size()) {
return findKth(nums2, nums1, k);
}

<span class="c1">// 情况1：nums1 为空，直接返回 nums2 的第 k 小元素

if (nums1.empty()) {
return nums2[k - 1];
}

<span class="c1">// 情况2：找第 1 小元素，返回两个区间首元素的最小值

if (k == 1) {
return min(nums1[0], nums2[0]);
}

<span class="c1">// 计算要比较的步长（取 k/2 和区间长度的较小值，防止越界）

int i = min(static_cast<size_t>(k / 2), nums1.size());
int j = k - i;

<span class="c1">// 比较两个区间的第 i/j 个元素，排除不可能包含第 k 小的部分

if (nums1[i - 1] < nums2[j - 1]) {
// 排除 nums1 的前 i 个元素，传递 nums1[i…] 的切片
return findKth(nums1.subspan(i), nums2, k - i);
} else {
// 排除 nums2 的前 j 个元素，传递 nums2[j…] 的切片
return findKth(nums1, nums2.subspan(j), k - j);
}
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
size_t m = nums1.size();
size_t n = nums2.size();
// 奇数长度取中间一个，偶数长度取中间两个的平均值
int k1 = (m + n + 1) / 2;
int k2 = (m + n + 2) / 2;

<span class="c1">// 将 vector 转为 span，直接传递区间

int num1 = findKth(span(nums1), span(nums2), k1);
int num2 = findKth(span(nums1), span(nums2), k2);

<span class="k">return</span> <span class="p">(</span><span class="n">num1</span> <span class="o">+</span> <span class="n">num2</span><span class="p">)</span> <span class="o">/</span> <span class="mf">2.0</span><span class="p">;</span>

}

// 测试用例
int main() {
vector<int> nums1 = {1, 3};
vector<int> nums2 = {2};
cout << “中位数：” << findMedianSortedArrays(nums1, nums2) << endl; // 输出 2.0

vector<int> nums3 = {1, 2};
vector<int> nums4 = {3, 4};
cout << “中位数：” << findMedianSortedArrays(nums3, nums4) << endl; // 输出 2.5
return 0;
}