当前位置:网站首页>【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--;
}
}
};
总结
这道题是面试中的常考题,核心思想就是从后向前遍历数组,避免数据被覆盖。如果从前往后遍历就需要定义一个数组,会造成空间的浪费。
边栏推荐
- 2022 China Soft Drink Market Insights
- 关于#sql#的问题:怎么将下面的数据按逗号分隔成多行,以列的形式展示出来
- 国密规范 SM2 SM3 SM4
- 年薪40W测试工程师成长之路,你在哪个阶段?
- 3.2 - classification - Logistic regression
- Hibernate 的 Session 缓存相关操作
- Pytorch模型转ONNX模型
- Write a resume like this, easy to get the interviewer
- Find the latest staff salary and the last staff salary changes
- Serverless + domain name can also build a personal blog? Really, and soon
猜你喜欢

详述MIMIC 的ICU患者检测时间信息表(十六)

1096 big beautiful numbers (15 points)

1101 How many times B is A (15 points)

Distributed Lock-Redission - Cache Consistency Solution

【LeetCode每日一题】——682.棒球比赛

【Pytorch】nn.PixelShuffle

1036 跟奥巴马一起编程 (15 分)

TF generates (feature, label) set through feature and label, tf.data.Dataset.from_tensor_slices

TF中使用softmax函数;
2.1-梯度下降
随机推荐
语音信号处理:预处理【预加重、分帧、加窗】
恒源云-Pycharm远程训练避坑指南
3.1-Classification-probabilistic generative model
【LeetCode】Summary of linked list problems
leetcode:69. x 的平方根
Distributed Lock-Redission - Cache Consistency Solution
1071 Small Gamble (15 points)
1106 2019 Sequence (15 points)
【latex异常和错误】Missing $ inserted.<inserted text>You can‘t use \spacefactor in math mode.输出文本要注意特殊字符的转义
JRS303-数据校验
1003 我要通过 (20 分)
2021-08-11 for循环结合多线程异步查询并收集结果
DDR4内存条电路设计
LeetCode brushing series -- 46. Full arrangement
从苹果、SpaceX等高科技企业的产品发布会看企业产品战略和敏捷开发的关系
我的创作纪念日丨感恩这365天来有你相伴,不忘初心,各自精彩
2022-08-10 mysql/stonedb-慢SQL-Q16-耗时追踪
1.1-回归
Service的两种状态形式
欢迎加入sumarua网络安全交流社区