promotion for 35 years coder-Day12-合并有序数组
2021/8/6 23:09:51
本文主要是介绍promotion for 35 years coder-Day12-合并有序数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream>
#include <string.h>
using namespace std;
//base:array1d的实际空间长度等于两个数组长度之和
//空间复杂度O(n),即归并排序
void merge1(int *array1, int len1, int *array2, int len2)
{
int *arrayTmp = new int[len1];
memcpy(arrayTmp, array1, len1 * sizeof(int));
int p1 = 0;
int p2 = 0;
int pTmp = 0;
while (p1 < len1 && p2 < len2)
{
array1[pTmp++] = arrayTmp[p1] < array2[p2] ? arrayTmp[p1++] : array2[p2++];
}
if (p1 < len1)
{
memcpy(array1 + pTmp, arrayTmp + p1, (len1 - p1) * sizeof(int));
}
if (p2 < len2)
{
memcpy(array1 + pTmp, array2 + p2, (len2 - p2) * sizeof(int));
}
delete arrayTmp;
}
//空间复杂度O(1),双指针,array1后面都是占位的0,因此从数组的最后一位开始遍历,从大往小,开始放值
void merge2(int *array1, int len1, int * array2, int len2)
{
int p1 = len1 - 1;
int p2 = len2 - 1;
int p = len1 + len2 -1;
while (p1 >= 0 && p2 >= 0)
{
array1[p--] = array1[p1] > array2[p2] ? array1[p1--] : array2[p2--];
}
if (p2 >= 0)
{
memcpy(array1, array2, (p2 + 1) * sizeof(int));
}
}
int main() {
int a1[10] = {0,1,3,5,7,9,0,0,0,0};
int a2[4] = {2,4,6,8};
//int a1[10] = {2,3,0,0,0,0,0,0,0,0};
//int a2[8] = {0,1,4,5,6,7,8,9};
//merge1(a1, 2, a2, 8);
merge2(a1, 6, a2, 4);
for (int i = 0; i < 10; i++)
cout << a1[i] << endl;
return 0;
}
这篇关于promotion for 35 years coder-Day12-合并有序数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享