湖北省网站建设_网站建设公司_MySQL_seo优化

LeetCode 4. 寻找两个正序数组的中位数

---

一、题目描述

原题

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

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

示例

示例	输入	输出	解释
1	nums1 = [1,3], nums2 = [2]	2.0	合并数组 = [1,2,3]，中位数是 2
2	nums1 = [1,2], nums2 = [3,4]	2.5	合并数组 = [1,2,3,4]，中位数是 (2+3)/2 = 2.5
3	nums1 = [0,0], nums2 = [0,0]	0.0	合并数组 = [0,0,0,0]，中位数是 0
4	nums1 = [], nums2 = [1]	1.0	只有一个元素
5	nums1 = [2], nums2 = []	2.0	只有一个元素

约束条件

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

---

二、题目解析

核心问题拆解

维度	分析内容
输入	两个已排序的数组，可能有一个为空
输出	浮点数，表示中位数
中位数定义	奇数个元素取中间，偶数个元素取中间两数平均值
关键约束	时间复杂度要求 O(log(m+n))，暗示需要二分法
边界条件	数组为空、单元素、长度差异大

中位数性质

总长度	中位数位置	计算方式
奇数 (2k+1)	第 k+1 个	直接取值
偶数 (2k)	第 k 和 k+1 个	取平均值

思考方向流程图

flowchart TDA["原问题: 两数组中位数"] --> B{"如何找中位数"}B --> C["方法1: 合并后排序"]B --> D["方法2: 双指针归并"]B --> E["方法3: 二分查找第K小"]B --> F["方法4: 二分划分数组"]C --> C1["时间 O m+n"]C1 --> C2["不满足要求"]D --> D1["时间 O m+n"]D1 --> D2["不满足要求"]E --> E1["时间 O log m+n"]E1 --> E2["满足要求"]F --> F1["时间 O log min m,n"]F1 --> F2["最优解"]style A fill:#e1f5festyle C2 fill:#ffcdd2style D2 fill:#ffcdd2style E2 fill:#c8e6c9style F2 fill:#c8e6c9

---

三、算法解答

---

解法一：合并排序法（暴力）

1. 算法原理描述

核心思想：将两个数组合并成一个有序数组，然后直接取中位数。

实现方式：

• 利用归并排序的合并思想
• 双指针遍历两个数组，按顺序放入新数组
• 根据总长度的奇偶性计算中位数

2. 算法解答过程

以 nums1 = [1,3], nums2 = [2] 为例：

步骤	i	j	比较	merged数组	操作
1	0	0	1 < 2	[1]	取nums1[0]
2	1	0	3 > 2	[1,2]	取nums2[0]
3	1	1	-	[1,2,3]	取nums1[1]
结果	-	-	-	[1,2,3]	中位数 = 2

3. 算法原理图像解析

flowchart LRsubgraph Merge["合并过程"]A["nums1: 1, 3"] --> C["比较头部元素"]B["nums2: 2"] --> CC --> D["取较小者放入merged"]D --> E["移动对应指针"]E --> Cendsubgraph Result["结果"]F["merged: 1, 2, 3"] --> G["长度=3 奇数"]G --> H["中位数 = merged 1 = 2"]endMerge --> Result

4. 算法代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();vector<int> merged(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;}}
};

5. 代码详解

关键点	说明
双指针 i, j	分别遍历两个数组
merged[k++]	按顺序放入合并数组
total % 2	判断奇偶决定取法
/2.0	保证返回浮点数

6. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(m+n)	遍历两个数组各一次
空间复杂度	O(m+n)	需要额外数组存储

7. 使用范围

• 简单直观，适合理解题意
• 不满足题目O(log(m+n))的要求
• 面试中需要说明这是初步解法

---

解法二：双指针优化（不存储）

1. 算法原理描述

核心思想：不需要真正合并数组，只需要找到第 (m+n)/2 个和第 (m+n)/2+1 个元素。

实现方式：

• 双指针模拟归并过程
• 只记录需要的两个位置的值
• 不需要额外数组存储

2. 算法解答过程

以 nums1 = [1,2], nums2 = [3,4] 为例，总长度4，需要找第2和第3个元素：

步骤	i	j	当前值	count	left	right	说明
1	0	0	1	1	0	1	取nums1[0]=1
2	1	0	2	2	1	2	取nums1[1]=2, 到达位置1
3	2	0	3	3	2	3	取nums2[0]=3, 到达位置2
结果	-	-	-	-	2	3	中位数 = (2+3)/2 = 2.5

3. 算法代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();int total = m + n;int left = 0, right = 0;  // 记录中间两个数int i = 0, j = 0;// 遍历到中间位置for (int count = 0; count <= total / 2; count++) {left = right;  // 保存前一个值if (i < m && (j >= n || nums1[i] <= nums2[j])) {right = nums1[i++];} else {right = nums2[j++];}}// 根据奇偶返回结果if (total % 2 == 1) {return right;} else {return (left + right) / 2.0;}}
};

4. 代码详解

关键点	说明
left, right	记录相邻的两个中间值
left = right	滚动更新，保存前一个值
j >= n	处理nums2已遍历完的情况

5. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(m+n)	最多遍历 (m+n)/2 次
空间复杂度	O(1)	只用常数空间

6. 使用范围

• 空间优化版本
• 仍不满足时间复杂度要求
• 作为过渡解法展示优化思路

---

解法三：二分查找第K小元素

1. 算法原理描述

核心思想：将问题转化为"寻找两个有序数组中第K小的元素"，使用二分法每次排除 k/2 个元素。

关键洞察：

• 比较 nums1[k/2-1] 和 nums2[k/2-1]
• 较小的那个及其之前的元素一定不是第K小
• 每次可以排除 k/2 个元素，时间复杂度 O(log k)

2. 算法解答过程

以 nums1 = [1,3,5,7], nums2 = [2,4,6,8] 为例，找第5小（中位数位置）：

轮次	k	k/2	nums1范围	nums2范围	比较	排除
1	5	2	[1,3,5,7]	[2,4,6,8]	3 < 4	nums1前2个
2	3	1	[5,7]	[2,4,6,8]	5 > 2	nums2前1个
3	2	1	[5,7]	[4,6,8]	5 > 4	nums2前1个
4	1	-	[5,7]	[6,8]	-	取min(5,6)=5

3. 算法原理图像解析

flowchart TDA["找第K小元素"] --> B["比较 nums1 k/2-1 和 nums2 k/2-1"]B --> C{"哪个更小"}C -->|nums1更小| D["排除nums1前k/2个元素"]C -->|nums2更小| E["排除nums2前k/2个元素"]C -->|相等| F["排除任意一个的前k/2个"]D --> G["k = k - k/2"]E --> GF --> GG --> H{"k == 1"}H -->|否| BH -->|是| I["返回两数组当前位置较小值"]style A fill:#e3f2fdstyle I fill:#c8e6c9

4. 算法代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();int total = m + n;if (total % 2 == 1) {// 奇数：找第 (total+1)/2 小return getKth(nums1, 0, nums2, 0, total / 2 + 1);} else {// 偶数：找第 total/2 和 total/2+1 小的平均值int left = getKth(nums1, 0, nums2, 0, total / 2);int right = getKth(nums1, 0, nums2, 0, total / 2 + 1);return (left + right) / 2.0;}}private:// 找两个数组中第k小的元素int getKth(vector<int>& nums1, int start1, vector<int>& nums2, int start2, int k) {int len1 = nums1.size() - start1;int len2 = nums2.size() - start2;// 保证 len1 <= len2，简化边界处理if (len1 > len2) {return getKth(nums2, start2, nums1, start1, k);}// 边界情况1：nums1已经用完if (len1 == 0) {return nums2[start2 + k - 1];}// 边界情况2：k=1，返回两数组当前最小值if (k == 1) {return min(nums1[start1], nums2[start2]);}// 计算要比较的位置（不能超过数组长度）int i = start1 + min(len1, k / 2) - 1;int j = start2 + min(len2, k / 2) - 1;if (nums1[i] <= nums2[j]) {// 排除 nums1[start1..i]return getKth(nums1, i + 1, nums2, start2, k - (i - start1 + 1));} else {// 排除 nums2[start2..j]return getKth(nums1, start1, nums2, j + 1, k - (j - start2 + 1));}}
};

5. 代码详解

关键点	说明
len1 > len2 交换	保证第一个数组更短，简化边界
len1 == 0	短数组用完，直接从长数组取
k == 1	递归终止，取两者最小值
min(len1, k/2)	防止数组越界
k - (i - start1 + 1)	更新k，减去排除的元素个数

6. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(log(m+n))	每次排除k/2个元素
空间复杂度	O(log(m+n))	递归调用栈深度

7. 使用范围

• 满足题目时间复杂度要求
• 思路清晰，易于理解
• 面试中的推荐解法

---

解法四：二分划分法（最优解）

1. 算法原理描述

核心思想：将两个数组各划分为左右两部分，使得：

1. 左半部分元素个数 = 右半部分元素个数（或多1个）
2. 左半部分所有元素 <= 右半部分所有元素

关键公式：

• 设 nums1 划分位置为 i，nums2 划分位置为 j
• 满足：i + j = (m + n + 1) / 2
• 条件：nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]

2. 划分示意图

nums1:  [a1, a2, ..., a(i-1)] | [ai, ..., am]i
nums2:  [b1, b2, ..., b(j-1)] | [bj, ..., bn]j左半部分: a1...a(i-1), b1...b(j-1)  共 i+j 个
右半部分: ai...am, bj...bn          共 m+n-i-j 个中位数 = max(左半部分)  或  (max(左) + min(右)) / 2

3. 算法解答过程

以 nums1 = [1,3,8,9], nums2 = [2,4,5,6,7] 为例：

轮次	i	j	左边最大	右边最小	条件检查	调整
初始	lo=0, hi=4	-	-	-	-	-
1	2	3	max(3,5)=5	min(8,6)=6	3<=6 ✓, 5<=8 ✓	找到

结果：左边最大=5，右边最小=6，总长度9（奇数），中位数=5

4. 算法原理图像解析

flowchart TDA["在较短数组上二分"] --> B["计算划分位置 i"]B --> C["j = halfLen - i"]C --> D{"检查划分是否有效"}D --> E{"i太小: nums1 i-1 > nums2 j"}D --> F{"i太大: nums2 j-1 > nums1 i"}D --> G{"划分正确"}E --> H["lo = i + 1"]F --> I["hi = i - 1"]G --> J["计算中位数"]H --> BI --> BJ --> K{"总长度奇偶"}K -->|奇数| L["返回 max of 左半部分"]K -->|偶数| M["返回 max左 + min右 / 2"]style A fill:#e3f2fdstyle L fill:#c8e6c9style M fill:#c8e6c9

5. 算法代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {// 保证 nums1 是较短的数组if (nums1.size() > nums2.size()) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.size();int n = nums2.size();// 在 nums1 上进行二分查找int lo = 0, hi = m;int halfLen = (m + n + 1) / 2;while (lo <= hi) {int i = lo + (hi - lo) / 2;  // nums1 的划分位置int j = halfLen - i;          // nums2 的划分位置// 边界值处理int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];int nums1RightMin = (i == m) ? INT_MAX : nums1[i];int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];int nums2RightMin = (j == n) ? INT_MAX : nums2[j];if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {// 找到正确的划分if ((m + n) % 2 == 1) {return max(nums1LeftMax, nums2LeftMax);} else {return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2.0;}} else if (nums1LeftMax > nums2RightMin) {// i 太大，需要减小hi = i - 1;} else {// i 太小，需要增大lo = i + 1;}}return 0.0;  // 不会到达这里}
};

6. 代码详解

关键点	说明
保证 nums1 较短	在较短数组上二分，效率更高
halfLen = (m+n+1)/2	+1 处理奇数情况，使左半部分多1个
INT_MIN / INT_MAX	处理边界，i=0 或 i=m 的情况
二分调整	根据交叉比较结果调整搜索范围

核心条件解释：

// 有效划分必须满足：
// 1. nums1[i-1] <= nums2[j]  (左1 <= 右2)
// 2. nums2[j-1] <= nums1[i]  (左2 <= 右1)// 如果 nums1[i-1] > nums2[j]，说明 i 太大
// 如果 nums2[j-1] > nums1[i]，说明 i 太小

7. 复杂度分析

复杂度类型	值	说明
时间复杂度	O(log(min(m,n)))	只在较短数组上二分
空间复杂度	O(1)	只用常数空间

8. 使用范围

• 最优解法，时间和空间都最优
• 面试中的加分解法
• 理解难度较高，需要充分准备

---

四、算法对比

解法	时间复杂度	空间复杂度	优点	缺点	推荐指数
合并排序	O(m+n)	O(m+n)	直观易懂	不满足要求	⭐⭐
双指针	O(m+n)	O(1)	空间优化	不满足要求	⭐⭐
二分第K小	O(log(m+n))	O(log(m+n))	满足要求，易理解	递归栈空间	⭐⭐⭐⭐
二分划分	O(log(min(m,n)))	O(1)	最优解	理解难度高	⭐⭐⭐⭐⭐

推荐选择

flowchart LRA["选择解法"] --> B{"面试时间"}B -->|紧张| C["二分第K小"]B -->|充裕| D["二分划分法"]C --> E["思路清晰易讲解"]D --> F["展示最优解能力"]style C fill:#c8e6c9style D fill:#fff9c4

---

五、知识点总结

涉及的数据结构

数据结构	用途	说明
有序数组	输入数据	已排序是解题关键
双指针	归并遍历	模拟合并过程
虚拟划分	二分思想	不实际划分，只计算位置

涉及的算法思想

flowchart TBsubgraph Core["二分查找核心"]A["有序性"] --> A1["数组已排序"]A --> A2["单调性决定搜索方向"]endsubgraph Transform["问题转化"]B1["中位数 -> 第K小"]B2["两数组 -> 划分问题"]endsubgraph Technique["关键技巧"]C1["每次排除一半元素"]C2["交叉比较判断有效性"]C3["边界值用极值处理"]endsubgraph Complexity["复杂度分析"]D1["log级别来自二分"]D2["在较短数组上二分更优"]endCore --> TransformTransform --> TechniqueTechnique --> Complexity

相关语言知识点

C++ 知识点	说明
INT_MIN / INT_MAX	整型极值，处理边界
vector.size()	获取数组长度
(lo + hi) / 2	防溢出写法：lo + (hi-lo)/2
引用传参	vector<int>& 避免拷贝
递归	二分第K小解法使用递归

---

六、做题模板

二分查找第K小模板

// 在两个有序数组中找第K小的元素
int getKth(vector<int>& nums1, int start1,vector<int>& nums2, int start2, int k) {int len1 = nums1.size() - start1;int len2 = nums2.size() - start2;// 保证 len1 <= len2if (len1 > len2) {return getKth(nums2, start2, nums1, start1, k);}// 边界：数组用完if (len1 == 0) return nums2[start2 + k - 1];// 边界：k = 1if (k == 1) return min(nums1[start1], nums2[start2]);// 计算比较位置int i = start1 + min(len1, k / 2) - 1;int j = start2 + min(len2, k / 2) - 1;// 排除较小方的元素if (nums1[i] <= nums2[j]) {return getKth(nums1, i + 1, nums2, start2, k - (i - start1 + 1));} else {return getKth(nums1, start1, nums2, j + 1, k - (j - start2 + 1));}
}

二分划分模板

// 两有序数组的划分二分
double findMedian(vector<int>& nums1, vector<int>& nums2) {if (nums1.size() > nums2.size()) swap(nums1, nums2);int m = nums1.size(), n = nums2.size();int lo = 0, hi = m;int halfLen = (m + n + 1) / 2;while (lo <= hi) {int i = lo + (hi - lo) / 2;int j = halfLen - i;int L1 = (i == 0) ? INT_MIN : nums1[i-1];int R1 = (i == m) ? INT_MAX : nums1[i];int L2 = (j == 0) ? INT_MIN : nums2[j-1];int R2 = (j == n) ? INT_MAX : nums2[j];if (L1 <= R2 && L2 <= R1) {// 找到有效划分if ((m + n) % 2 == 1) return max(L1, L2);return (max(L1, L2) + min(R1, R2)) / 2.0;} else if (L1 > R2) {hi = i - 1;} else {lo = i + 1;}}return 0.0;
}

算法流程图

flowchart TDA["输入: nums1, nums2"] --> B["保证 nums1 较短"]B --> C["初始化 lo=0, hi=m"]C --> D["计算 i = lo+hi /2"]D --> E["计算 j = halfLen - i"]E --> F["获取四个边界值 L1 R1 L2 R2"]F --> G{"L1<=R2 且 L2<=R1"}G -->|是| H["计算并返回中位数"]G -->|否| I{"L1 > R2"}I -->|是| J["hi = i - 1"]I -->|否| K["lo = i + 1"]J --> DK --> Dstyle A fill:#e3f2fdstyle H fill:#c8e6c9

---

七、相关题目推荐

题号	题目名称	难度	关联知识点
33	搜索旋转排序数组	中等	二分查找变体
34	在排序数组中查找元素的第一个和最后一个位置	中等	二分边界
35	搜索插入位置	简单	二分基础
74	搜索二维矩阵	中等	二分应用
153	寻找旋转排序数组中的最小值	中等	二分查找
215	数组中的第K个最大元素	中等	第K大问题
287	寻找重复数	中等	二分思想
378	有序矩阵中第K小的元素	中等	二分+第K小
719	找出第K小的数对距离	困难	二分答案
1060	有序数组中的缺失元素	中等	二分查找

---

八、面试高频问答

Q1: 为什么要在较短的数组上二分？

答：

• 时间复杂度从 O(log(m+n)) 优化到 O(log(min(m,n)))
• 减少边界判断的复杂度
• j = halfLen - i，如果 i 的范围小，j 越界的可能性也小

Q2: halfLen 为什么是 (m+n+1)/2 而不是 (m+n)/2？

答：

+1 的作用是处理奇数情况，使左半部分多一个元素总长度 = 5: halfLen = 3, 左边3个，右边2个
总长度 = 6: halfLen = 3, 左边3个，右边3个这样奇数时直接返回 max(左边)，偶数时返回 (max左 + min右) / 2

Q3: INT_MIN 和 INT_MAX 的作用？

答：

• 当 i=0 时，nums1 的左边没有元素，用 INT_MIN 表示
• 当 i=m 时，nums1 的右边没有元素，用 INT_MAX 表示
• 这样比较 L1 <= R2 时不需要特殊判断边界

Q4: 如何证明一定能找到有效划分？

答：

• 因为两个数组都是有序的
• 当 i 从 0 移动到 m 时，L1 单调增加，R1 也单调增加
• 同时 j 从 halfLen 减少到 halfLen-m，L2 单调减少，R2 也单调减少
• 存在一个交点使得 L1<=R2 且 L2<=R1

Q5: 时间复杂度为什么是 O(log(min(m,n)))？

答：

• 二分查找在长度为 min(m,n) 的数组上进行
• 每次迭代将搜索范围减半
• 所以是 O(log(min(m,n)))

Q6: 这道题和"第K小元素"有什么关系？

答：

中位数位置	第K小
奇数长度 n	第 (n+1)/2 小
偶数长度 n	第 n/2 和 n/2+1 小的平均

所以中位数问题可以转化为1-2次"第K小"问题。

---

九、一图总结

flowchart TBsubgraph KeyPoint["核心要点"]A["两数组中位数"] --> B["问题转化"]B --> B1["转为第K小问题"]B --> B2["转为划分问题"]endsubgraph Method["核心方法"]C["二分查找"] --> C1["每次排除k/2个元素"]C --> C2["在短数组上划分"]endsubgraph Key["关键点"]D1["保证短数组在前"]D2["halfLen = m+n+1 / 2"]D3["边界用极值处理"]D4["交叉比较判断有效"]endsubgraph Complexity["复杂度"]E["时间 O log min m,n"]F["空间 O 1"]endKeyPoint --> MethodMethod --> KeyKey --> Complexitystyle A fill:#e1f5festyle E fill:#c8e6c9style F fill:#c8e6c9

---

速记卡片

项目	内容
题目	LeetCode 4 - 两正序数组中位数
难度	困难
核心思想	二分划分 / 二分第K小
时间复杂度	O(log(min(m,n)))
空间复杂度	O(1)
关键公式	i + j = (m + n + 1) / 2
有效条件	L1 <= R2 && L2 <= R1
边界处理	INT_MIN 和 INT_MAX

---

记忆口诀

口诀	含义
短数组上做二分	在较短数组上二分效率更高
划分左右数相等	i + j = halfLen 保证左右平衡
交叉比较定有效	L1<=R2 且 L2<=R1 才是有效划分
极值处理边界清	用 INT_MIN/MAX 简化边界判断

---

核心代码速记

// 核心：在短数组上二分找划分点
int i = lo + (hi - lo) / 2;  // nums1的划分点
int j = halfLen - i;          // nums2的划分点// 有效性判断
if (L1 <= R2 && L2 <= R1) {// 找到答案return (m+n) % 2 ? max(L1,L2) : (max(L1,L2)+min(R1,R2))/2.0;
} else if (L1 > R2) {hi = i - 1;  // i太大
} else {lo = i + 1;  // i太小
}

---

💡 面试建议：这道题是Hard难度的经典题，建议先讲解"二分第K小"的思路（更直观），再优化到"二分划分"（最优解）。关键是要能清晰解释为什么每次可以排除k/2个元素，以及划分有效性的判断条件。