当前位置: 首页 > web >正文

数据结构:数组:合并数组(Merging Arrays)

目录

第一步:明确问题本质

第二步:从最朴素的思考出发

第三步:利用“有序性” —— 双指针思想

 第四步:代码实现

🤔 为什么sizeof(A) 是整个数组的字节大小? 

第五步:复杂度分析


第一步:明确问题本质

我们的问题是:

给定两个有序数组 A 和 B,合并成一个新的有序数组 C。

 输入:

  • 数组 A = [1, 3, 5](已排序)

  • 数组 B = [2, 4, 6](已排序)

 目标:

  • 输出数组 C = [1, 2, 3, 4, 5, 6](也是升序排列)

第二步:从最朴素的思考出发

假设我们是个完全不懂算法的人,我们也知道一个最直接的想法:

把两个数组接在一起,然后对它排序!

思路大概是这样:

int A[3] = {1, 3, 5};
int B[3] = {2, 4, 6};C = A + B           // 合并:C = [1, 3, 5, 2, 4, 6]
C.sort()            // 排序:C = [1, 2, 3, 4, 5, 6]

✅ 正确,但:

  • 时间复杂度为 O((m+n) log (m+n))

  • 没有利用“原数组已排序”这一信息。

第三步:利用“有序性” —— 双指针思想

这是我们“从零开始”的第一个优化:用两个指针分别指向两个数组的起始位置。

📍关键想法:

我们想象两个手指:

  • 一个指向 A 的当前元素(叫 i

  • 一个指向 B 的当前元素(叫 j

我们每次比较 A[i]B[j],把较小的那个放进结果数组 C,然后把对应的指针向前移动一步。

这样我们就一步步构造了有序数组 C,直到 A 和 B 的元素都被用完。

 第四步:代码实现

第一步:定义数组 & 初始变量

#include <iostream>
using namespace std;int main() {int A[] = {1, 3, 5};int B[] = {2, 4, 6};int m = sizeof(A) / sizeof(A[0]);int n = sizeof(B) / sizeof(B[0]);int C[m + n];  // 合并后数组
  • sizeof(A) 是整个数组的字节大小

  • sizeof(A[0]) 是一个元素的字节大小

  • 所以 m 是 A 的元素个数(同理 B 的个数是 n

🤔 为什么sizeof(A) 是整个数组的字节大小? 

在定义的时候:

int A[] = {1, 2, 3};

此时 A 是一个“数组变量名”,编译器知道 A 是长度为 3 的整型数组,是固定内存块,sizeof(A) 是数组大小:3 × sizeof(int)

但在其他地方,比如:

int* ptr = A;

 这里 A 的确是 数组名退化成了指针。它变成了指向第一个元素的指针 &A[0],但它本身不是个指针变量。

总结:数组和指针的差异

场景A 是什么?sizeof(A) 返回原因
定义处 int A[3];数组整个数组字节数编译期知道大小
函数参数 void foo(int A[])指针指针大小(4/8字节)退化成 int*
int* p = A;指针指针大小A 自动退化成指针

数组名在定义时不是指针,是整个数组;在表达式中是指针,是地址。 

 第二步:双指针合并逻辑

while (i < m && j < n) {if (A[i] < B[j]) {C[k] = A[i];i++;} else {C[k] = B[j];j++;}k++;
}
  • 每次比较 A[i] 和 B[j] 谁更小

  • 小的放到 C[k],移动对应指针

  • k 永远负责指向 C 的下一个空位

第三步:处理剩余元素 

while (i < m) {C[k] = A[i];i++;k++;
}while (j < n) {C[k] = B[j];j++;k++;
}
  • 可能 A 或 B 有剩下的没合并完(另一个已经走完了)

  • 全部照顺序复制进 C

 完整代码

#include <iostream>
using namespace std;int main() {int A[] = {1, 3, 5};int B[] = {2, 4, 6};int m = sizeof(A) / sizeof(A[0]);int n = sizeof(B) / sizeof(B[0]);int C[100];  // 假设长度不会超出 100int i = 0, j = 0, k = 0;// 双指针合并while (i < m && j < n) {if (A[i] < B[j]) {C[k] = A[i];i++;} else {C[k] = B[j];j++;}k++;}// 把剩余的 A 复制进去while (i < m) {C[k] = A[i];i++;k++;}// 把剩余的 B 复制进去while (j < n) {C[k] = B[j];j++;k++;}// 输出合并后的结果cout << "Merged Array: ";for (int x = 0; x < m + n; x++) {cout << C[x] << " ";}cout << endl;return 0;
}

第五步:复杂度分析

项目分析
时间复杂度O(m + n),每个元素只访问一次
空间复杂度O(m + n),结果数组 C
http://www.xdnf.cn/news/15046.html

相关文章:

  • 大学人才引进初试试题(开卷)
  • IDEA Maven报错 无法解析 com.taobao:parent:pom:1.0.1【100%解决 此类型问题】
  • Amazon Lightsail 全解析:中小企业上云
  • 【AI智能体】智能音视频-基于乐鑫 ESP32 实现音视频通话
  • 数据库|达梦DM数据库配置实例步骤
  • 【读论文】GLM-4.1V-Thinking 解读:用强化学习解锁 VLM 的通用推理能力
  • 转换狂魔,Modbus TCP转Profinet网关打通视觉传感线连接之路
  • Sigmoid Loss for Language Image Pre-Training
  • Java教程:【程序调试技巧】入门
  • Paimon本地表查询引擎LocalTableQuery详解
  • Spring AI:ETL Pipeline
  • pytorch深度学习-ResNet残差网络-CIFAR-10
  • Terraform `for_each` 精讲:优雅地自动化多域名证书验证
  • el-button传入icon用法可能会出现的问题
  • 【ES实战】ES客户端线程量分析
  • 3423. 循环数组中相邻元素的最大差值 — day97
  • OpenCV在Visual Studio 2022下的配置
  • loam的scanRegistration.cpp文件学习
  • 深度剖析:Ceph分布式存储系统架构
  • Html+Css+JavaScript+Vue+Axios入门
  • 计算机网络:(八)网络层(中)IP层转发分组的过程与网际控制报文协议 ICMP
  • 【计算机网络】第三章:数据链路层(上)
  • 数与运算-埃氏筛 P1835 素数密度
  • Python入门笔记
  • 容器技术技术入门与Docker环境部署
  • JavaScript中的Request详解:掌握Fetch API与XMLHttpRequest
  • 微前端框架对比
  • unity 模型UV重叠问题相关(重新整理)
  • web网页,在线%发布,智能投稿,新闻系统%分析系统demo,基于aspnet,net,mvc,echart,sqlserver数据库
  • Spring Boot项目中整合MCP协议及实现AI应用实践