极客教程C++程序 合并三个排序数组
给定三个按升序排列的数组（A，B，C），我们需要将它们按升序合并在一起并输出数组D。
例子:
输入 : A = [1, 2, 3, 4, 5]
B = [2, 3, 4]
C = [4, 5, 6, 7]
输出 : D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]
输入 : A = [1, 2, 3, 5]
B = [6, 7, 8, 9 ]
C = [10, 11, 12]
输出 : D = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
方法一（每次合并两个数组）
我们已经讨论了合并2个排序数组的方法。所以我们可以先合并两个数组，然后再将结果与第三个数组合并。合并两个数组的时间复杂度为O（m + n）。因此，对于合并第三个数组，时间复杂度将变为O（m + n + o）。请注意，这确实是可以在此问题中实现的最佳时间复杂度。
空间复杂度 : 由于我们一次合并两个数组，因此我们需要另一个数组来存储第一次合并的结果。这将导致空间复杂度达到O（m + n）。请注意，在计算复杂度时忽略了保存3个数组结果所需的空间。
算法
function merge(A, B)
令m和n为A和B的大小
令D为存储结果的数组
//选取A和B中更小的元素进行合并
如果i < m并且j < n，那么
如果A[i] <= B[j]，
将A[i]添加到D中并将i加1
否则将B[j]添加到D中并将j加1
//如果数组A已经用尽，则添加来自B的元素
当j < n时
将B[j]添加到D中并将j加1
//如果数组B已经用尽，则添加来自A的元素
当i < n时
将A[j]添加到D中并将i加1
返回D
function merge_three(A, B, C)
T = merge(A, B)
return merge(T, C)
实现如下：
//C++程序，每次合并两个排序数组。
//C++ program to merge three sorted arrays by merging two at a time.
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
void printVector(const Vector& a)
{
cout << "[";
for (auto e : a)
cout << e << " ";
cout << "]" << endl;
}
Vector mergeTwo(Vector& A, Vector& B)
{
// Get sizes of vectors
int m = A.size();
int n = B.size();
// Vector for storing Result
Vector D;
D.reserve(m + n);
int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j])
D.push_back(A[i++]);
else
D.push_back(B[j++]);
}
// B已经走到头了
while (i < m)
D.push_back(A[i++]);
// A已经走到头了
while (j < n)
D.push_back(B[j++]);
return D;
}
//驱动程序
int main()
{
Vector A = { 1, 2, 3, 5 };
Vector B = { 6, 7, 8, 9 };
Vector C = { 10, 11, 12 };
//先合并A和B
Vector T = mergeTwo(A, B);
//合并T和C并打印结果
printVector(mergeTwo(T, C));
return 0;
}
输出：
[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
方法二（每次合并三个数组）
方法一的空间复杂度可以得到改善，我们将这三个数组合并在一起。
函数合并三个(A，B，C)
定义三个数组A，B，C的大小为m，n，o。
定义D数组用来存储合并的值。
// 同时合并三个数组
while i < m and j < n and k < o
找到A[i]、B[j]、C[k]的最小值
如果最小值来自A，将其添加到D中，i加1
如果最小值来自B，将其添加到D中，j加1
如果最小值来自C，将其添加到D中，k加1
// 以上步骤后，至少有一个数组已经为空，只有C数组为空了
while i < m and j < n
取A[i]和B[j]的最小值，将其插入到D中
如果最小值来自A，i加1，否则j加1
// 仅有B数组为空了
while i < m and k < o
取A[i]和C[k]的最小值，将其插入到D中
如果最小值来自A，i加1，否则k加1
// 仅有A数组为空了
while j < n and k < o
取B[j]和C[k]的最小值，将其插入到D中
如果最小值来自B，j加1，否则k加1
// 以上步骤后，在至少两个数组为空
如果A和B为空了，就从C中取元素
如果B和C为空了，就从A中取元素
如果A和C为空了，就从B中取元素
返回D
时间复杂度：时间复杂度为O(m+n+o),因为我们只处理每个数组中的元素一次。我们只需要一个数组来存储合并后的结果，因此消除了这个数组，空间复杂度是O(1)。
算法的实现如下：
// C++ program to merge three sorted arrays
// by merging three simultaneously.
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
void printVector(const Vector& a)
{
cout << "[";
for (auto e : a) {
cout << e << " ";
}
cout << "]" << endl;
}
Vector mergeThree(Vector& A, Vector& B,
Vector& C)
{
int m, n, o, i, j, k;
// 获取三个向量的大小
m = A.size();
n = B.size();
o = C.size();
// 用于存储结果的向量
Vector D;
D.reserve(m + n + o);
i = j = k = 0;
while (i < m && j < n && k < o) {
// 获取A、B、C中的最小值
int m = min(min(A[i], B[j]), C[k]);
// 将m添加到D中
D.push_back(m);
// 增加i、j、k
if (m == A[i])
i++;
else if (m == B[j])
j++;
else
k++;
}
// 这里C为空
while (i < m && j < n) {
if (A[i] <= B[j]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(B[j]);
j++;
}
}
// 这里B为空
while (i < m && k < o) {
if (A[i] <= C[k]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(C[k]);
k++;
}
}
// 这里A为空
while (j < n && k < o) {
if (B[j] <= C[k]) {
D.push_back(B[j]);
j++;
}
else {
D.push_back(C[k]);
k++;
}
}
// 这里A和B都为空
while (k < o)
D.push_back(C[k++]);
// 这里B和C都为空
while (i < m)
D.push_back(A[i++]);
// 这里A和C都为空
while (j < n)
D.push_back(B[j++]);
return D;
}
// 驱动代码
int main()
{
Vector A = { 1, 2, 41, 52, 84 };
Vector B = { 1, 2, 41, 52, 67 };
Vector C = { 1, 2, 41, 52, 67, 85 };
// 打印结果
printVector(mergeThree(A, B, C));
return 0;
}
输出结果
[1 1 1 2 2 2 41 41 41 52 52 52 67 67 84 85 ]
注意: 尽管实现合并两个或三个数组相对容易，但是如果要合并四个或更多个数组，则该过程变得麻烦。在这种情况下，我们应该遵循在合并K个已排序数组中显示的过程。
另一种方法（不关心耗尽的数组）：
可以通过以下代码缩短上面编写的代码。在这里，我们不需要编写任何数组的代码。
下面是上面方法的实现:
// C++ program to merge three sorted arrays
// Without caring about the exhausting array
#include <bits/stdc++.h>
using namespace std;
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
vector<int> merge3sorted(vector<int>& A, vector<int>& B,
vector<int>& C)
{
vector<int> ans;
int l1 = A.size();
int l2 = B.size();
int l3 = C.size();
int i = 0, j = 0, k = 0;
while (i < l1 || j < l2 || k < l3) {
// Assigning a, b, c with max values so that if
// any value is not present then also we can sort
// the array.
int a = INT_MAX, b = INT_MAX, c = INT_MAX;
// a, b, c variables are assigned only if the
// value exist in the array.
if (i < l1)
a = A[i];
if (j < l2)
b = B[j];
if (k < l3)
c = C[k];
// Checking if 'a' is the minimum
if (a <= b && a <= c) {
ans.push_back(a);
i++;
}
// Checking if 'b' is the minimum
else if (b <= a && b <= c) {
ans.push_back(b);
j++;
}
// Checking if 'c' is the minimum
else {
if (c <= a && c <= b) {
ans.push_back(c);
k++;
}
}
}
return ans;
}
// A utility function to print array list
void printeSorted(vector<int> list)
{
for (auto x : list)
cout << x << " ";
}
// Driver program to test above functions
int main()
{
vector<int> A = { 1, 2, 41, 52, 84 };
vector<int> B = { 1, 2, 41, 52, 67 };
vector<int> C = { 1, 2, 41, 52, 67, 85 };
vector<int> final_ans = merge3sorted(A, B, C);
printeSorted(final_ans);
return 0;
}
// This code is contributed by Pushpesh raj```
输出:
1 1 1 2 2 2 41 41 41 52 52 52 67 67 84 85
时间复杂度: O(m+n+o)，其中m、n和o是第1、第2和第3个数组的长度。
空间复杂度: O(m+n+o)，其中m、n和o是第1、第2和第3个数组的长度。用于输出数组的空间。