Leetcode 88:合并两个有序数组
2024-09-07 12:59:21
Leetcode链接 : https://leetcode-cn.com/problems/merge-sorted-array/
问题描述:
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3 输出:
[1,2,2,3,5,6]
解题思路:
数组一次遍历法:即反向遍历两个数组,每次获取两数组中的最大值,并按逆序在nums1中填充 ,程序时间复杂度O(m+n),空间复杂度O(1)。
解题步骤:
- 建立整型变量i , j 表示当前nums1和nums2的位置点,起始位置i=m-1, j=n-1
- 建立整型变量k,表示在num1中插入值的位置,起始位置m+n=1
- 比较num1[ i ]<nums2[ j ]是否成立,成立则nums1[ k ]=nums2[ j ],k=k-1,j=j-1 ; 否则nums1[ k ]=nums1[ i ],k=k-1,i=i-1 ;
- 直到 num1 或 num2 全部遍历完,若num2先遍历完,则此时 num1 已经全部有序。若num1先遍历完,则将num2中剩余的k个元素仍有序,将他们依次插入nums1中的0~k-1位置,程序结束。
若对过程仍不理解,请结合以下程序执行图进行理解,假设有两个数组为
nums1 = [1,4,7,0,0,0], nums2 = [2,5,8]
则程序执行过程如图所示:
该问题本质是寻找到当前剩余所有元素中的最大值然后插入nums1中,直到所有元素全部插完。
该问题C++实现代码
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=m-;
int j=n-;
int k=m+n-;
while(i>= && j>=){
if(nums1[i]<=nums2[j]){
nums1[k]=nums2[j];
j--;
k--;
}else{
nums1[k]=nums1[i];
i--;
k--;
}
}
while(j>=){
nums1[k]=nums2[j];
k--;
j--;
}
}
};
结束语:
此问题虽然只是一个简单的数组合并题,但仍有一些小的trick可供思考。因为本题要求的是原地插入nums1中,为何此处大小判别条件为:nums1[i]<=nums2[j],而不是nums1[i]<nums2[j],这两种条件都能保证程序输出正确的结果,这里卖个关子,希望有心的读者可以思考一下。
作图码字不易,如果对您有帮助,欢迎点击推荐关注(狗头)。。。
最新文章
- Manual——Test (翻译1)
- 重置zend studio 默认设置的方法
- Android 手机卫士4--设置中心显示
- Android入门篇1-Hello World
- python之旅【第二篇】
- Jenkins学习七:Jenkins的授权和访问控制
- [转载]ArcGIS Engine 中的多线程使用
- 通过js获取DropDownList的选中项
- 当linux遇上多网卡时
- soapUI参数中文乱码问题解决方法 (groovy脚本中文乱码)
- eclipse保存时自动格式化代码和优化导包
- Eclipse开发工具的使用之-使用Eclipse的Debug调试Android程序
- Detailed Information for Outputted Files from Somatic Mutation Annotators(annovar 注释文件条目详细解释)
- 叼叼叼,HTML5日期(Date)类型和文本(Text)类型互相转换
- css3自适应布局单位vw,vh你知道多少?
- 补充资料——自己实现极大似然估计(最大似然估计)MLE
- project6 PIT游戏
- 第二十六篇:USB3.0高带宽ISO(48KBytes/125us)实战
- 常见IT工具软件总结
- SimpleCursorAdapter和ListView的结合使用
热门文章
- nRF24L01+如何检测信道被占用-RSSI寄存器实战分享
- WC个人项目
- 有趣的bug——Java静态变量的循环依赖
- 查看UNDO 表空间使用情况
- mysql里面alter的用法
- 初学JavaScript正则表达式(十一)
- Tensorflow之变量赋值输出1+2+3+4+5+6+7+8+...
- [C9] 降维(Dimensionality Reduction)
- Linux学习笔记-第13天 最近有点跟不上节奏阿
- VScode Python 虚拟环境