当前位置:网站首页>【BM87 合并两个有序的数组】
【BM87 合并两个有序的数组】
2022-08-11 07:13:00 【安河桥畔】
合并两个有序的数组
题目来源
牛客网: 合并两个有序的数组
题目描述
给出一个有序的整数数组 A 和有序的整数数组 B ,请将数组 B 合并到数组 A 中,变成一个有序的升序数组
数据范围:|A_i| <=100∣A , |B_i| <= 100∣
注意:
1.保证 A 数组有足够的空间存放 B 数组的元素, A 和 B 中初始的元素数目分别为 m 和 n,A的数组空间大小为 m+n
2.不要返回合并的数组,将数组 B 的数据合并到 A 里面就好了,且后台会自动将合并后的数组 A 的内容打印出来,所以也不需要自己打印
3. A 数组在[0,m-1]的范围也是有序的
示例1
输入
[4,5,6],[1,2,3]
返回
[1,2,3,4,5,6]
说明
A数组为[4,5,6],B数组为[1,2,3],后台程序会预先将A扩容为[4,5,6,0,0,0],B还是为[1,2,3],m=3,n=3,传入到函数merge里面,然后请同学完成merge函数,将B的数据合并A里面,最后后台程序输出A数组
示例2
输入
[1,2,3],[2,5,6]
输出
[1,2,2,3,5,6]
思路分析
- A数组的容量能够放下两个数组所有的元素,所以可以不用定义新的数组
- 从后往前遍历向A数组中对应位置,放入A、B数组比较得到的较大值,从后往前遍历可以避免A数组前面的数据被覆盖
- 如果最后B数组有剩余元素没有放入A数组,则按顺序将剩下的元素放入A,若A有剩余保持不变即可
代码展示
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int i = m + n - 1;
m--;
n--;
while (n >= 0 && m >= 0)
{
//将大的数放入A数组最后的位置
if (A[m] >= B[n])
{
A[i] = A[m];
m--;
}
else
{
A[i] = B[n];
n--;
}
i--;
}
//循环结束后如果B数组由剩余,则将剩下的按顺序放入A数组中
while (n >= 0)
{
A[i] = B[n];
i--;
n--;
}
}
};
总结
这道题是面试中的常考题,核心思想就是从后向前遍历数组,避免数据被覆盖。如果从前往后遍历就需要定义一个数组,会造成空间的浪费。
边栏推荐
- 分布式锁-Redission - 缓存一致性解决
- 数仓开发知识总结
- Do you know the basic process and use case design method of interface testing?
- 支持各种文件快速重命名最简单的小技巧
- What are the things that should be planned from the beginning when developing a project with Unity?How to avoid a huge pit in the later stage?
- 【LeetCode每日一题】——844.比较含退格的字符串
- Distributed Lock-Redission - Cache Consistency Solution
- Activity的四种状态
- 欢迎加入sumarua网络安全交流社区
- Activity的四种启动模式
猜你喜欢
tf中矩阵乘法
关于#sql#的问题:怎么将下面的数据按逗号分隔成多行,以列的形式展示出来
经典论文-MobileNet V1论文及实践
Find the latest staff salary and the last staff salary changes
About # SQL problem: how to set the following data by commas into multiple lines, in the form of column display
Distributed Lock-Redission - Cache Consistency Solution
伦敦银规则有哪些?
The growth path of a 40W test engineer with an annual salary, which stage are you in?
Four operations in TF
1036 Programming with Obama (15 points)
随机推荐
项目1-PM2.5预测
【LeetCode每日一题】——844.比较含退格的字符串
tf中自减操作;tf.assign_sub()
1046 punches (15 points)
Production and optimization of Unity game leaderboards
接入网、承载网、核心网是什么,交换机路由器是什么、这个和网络的协议有什么关系呢?
redis操作
1.2-误差来源
【Pytorch】nn.PixelShuffle
基于微信小程序的租房小程序
Redis source code-String: Redis String command, Redis String storage principle, three encoding types of Redis string, Redis String SDS source code analysis, Redis String application scenarios
Test cases are hard?Just have a hand
js判断图片是否存在
JUC并发编程
Pytorch模型转ONNX模型
【sdx62】XBL设置共享内存变量,然后内核层获取变量实现
1.1-Regression
Pico neo3在Unity中的交互操作
How Unity programmers can improve their abilities
2022-08-10 mysql/stonedb-slow SQL-Q16-time-consuming tracking