C++程序 合并两个已排序的数组
给定两个已排序的数组,任务是以已排序的方式合并它们。
示例:
输入 : arr1[] = {1, 3, 4, 5},arr2[] = {2, 4, 6, 8}
输出 : arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
输入 : arr1[] = {5, 8, 9},arr2[] = {4, 7, 8}
输出 : arr3[] = {4, 5, 7, 8, 8, 9}
Naive Approach:
这是一种粗暴的方法来完成同样的操作。将arr1和arr2的所有元素放入arr3中,然后简单地对arr3进行排序。
以上方法的实现如下:
// C++ program to merge two sorted arrays/
#include<bits/stdc++.h>
using namespace std;
void mergeArrays(int arr1[], int arr2[], int n1,
int n2, int arr3[])
{
int i = 0, j = 0, k = 0;
// traverse the arr1 and insert its element in arr3
while(i < n1){
arr3[k++] = arr1[i++];
}
// now traverse arr2 and insert in arr3
while(j < n2){
arr3[k++] = arr2[j++];
}
// sort the whole array arr3
sort(arr3, arr3+n1+n2);
}
// Driver code
int main()
{
int arr1[] = {1, 3, 5, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {2, 4, 6, 8};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int arr3[n1+n2];
mergeArrays(arr1, arr2, n1, n2, arr3);
cout << "Array after merging" <<endl;
for (int i=0; i < n1+n2; i++)
cout << arr3[i] << " ";
return 0;
}
输出:
Array after merging
1 2 3 4 5 6 7 8
时间复杂度: O((m+n) log(m+n)) ,arr3的整个大小为m+n
辅助空间: O(1) ,没有使用额外的空间
方法2(O(n1 * n2)时间和O(n1+n2)额外空间)
- 创建一个大小为n1 + n2的数组arr3[]。
- 将arr1[]的所有n1个元素复制到arr3[]中
- 遍历arr2[]并一次将arr3[]的元素插入到arr1[]中(类似于插入排序)。这一步需要O(n1 * n2)的时间。
我们在 合并两个已排序的数组并使用O(1)额外空间的文章中讨论了上述方法的实现 。
方法3(O(n1 + n2)时间和O(n1 + n2)额外空间)
使用归并排序的Merge函数的想法。
- 创建一个大小为n1 + n2的数组arr3[]。
- 同时遍历arr1[]和arr2[]。
- 选择arr1[]和arr2[]中当前元素中较小的一个,将该较小的元素复制到arr3[]的下一个位置,并在arr3[]和所选数组中向前移动。
- 如果arr1[]或arr2[]中还有剩余元素,则也将它们复制到arr3[]中。
下面的图片是以上方法的运行结果:
下面是以上方法的实现:
// C++程序:合并两个排序数组/
# include<iostream>
using namespace std;
// 将 arr1[0..n1-1] 和 arr2[0..n2-1] 合并成 arr3[0..n1+n2-1]
void mergeArrays(int arr1[], int arr2[], int n1,
int n2, int arr3[])
{
int i = 0, j = 0, k = 0;
// 遍历两个数组
while (i<n1 && j <n2)
{
// 检查第一个数组的当前元素是否小于第二个数组的当前元素。
// 如果是,存储第一个数组元素并增加第一个数组索引;否则,用第二个数组做相同操作。
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
// 存储第一个数组中剩下的元素
while (i < n1)
arr3[k++] = arr1[i++];
// 存储第二个数组中剩下的元素
while (j < n2)
arr3[k++] = arr2[j++];
}
// 启动程序
int main()
{
int arr1[] = {1, 3, 5, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {2, 4, 6, 8};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int arr3[n1+n2];
mergeArrays(arr1, arr2, n1, n2, arr3);
cout << "Array after merging" <<endl;
for (int i=0; i < n1+n2; i++)
cout << arr3[i] << " ";
return 0;
}
输出
合并后的数组
1 2 3 4 5 6 7 8
输出:
合并后的数组
1 2 3 4 5 6 7 8
时间复杂度: O(n1 + n2)
空间复杂度: O(n1 + n2)
方法四:使用映射(O(nlog(n) + mlog(m)) 时间和 O(N) 额外空间)
- 将两个数组的元素作为键插入映射中。
- 打印映射的键。
以下是上述方法的实现。
// C++程序:使用映射合并两个排序数组
# include<bits/stdc++.h>
using namespace std;
// 合并数组的函数
void mergeArrays(int a[], int b[], int n, int m)
{
// 声明一个映射。
// 使用映射作为内置工具将元素存储在排序的顺序中。
map<int, int> mp;
// 将值插入到映射中。
for(int i = 0; i < n; i++)mp[a[i]]++;
for(int i = 0;i < m;i++)mp[b[i]]++;
// 打印映射的键。
for(auto j: mp)
{
for(int i=0; i<j.second;i++)cout<<j.first<<" ";
}
}
// 主函数
int main()
{
int a[] = {1, 3, 5, 7}, b[] = {2, 4, 6, 8};
int size = sizeof(a)/sizeof(int);
int size1 = sizeof(b)/sizeof(int);
// 调用函数
mergeArrays(a, b, size, size1);
return 0;
}
// 本代码由 yashbeersingh42 贡献```
输出
1 2 3 4 5 6 7 8
时间复杂度: O( nlog(n) + mlog(m) )
空间复杂度: O(N)