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[]和所选数组中向前移动。
1. 如果arr1[]或arr2[]中还有剩余元素，则也将它们复制到arr3[]中。

下面的图片是以上方法的运行结果：

C++程序合并两个已排序的数组

下面是以上方法的实现：

// 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 贡献```