合并 3 个排序的数组
给定 3 个按升序排列的数组A, B, C，我们需要将它们按升序合并在一起并输出数组D。
例子：
Input : A = [1, 2, 3, 4, 5]
B = [2, 3, 4]
C = [4, 5, 6, 7]
Output : D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]
Input : A = [1, 2, 3, 5]
B = [6, 7, 8, 9 ]
C = [10, 11, 12]
Output: D = [1, 2, 3, 5, 6, 7, 8, 9\. 10, 11, 12]
方法 1（一次两个数组）：
我们讨论了合并 2 个排序的数组。 因此，我们可以首先合并两个数组，然后将结果与第三个数组合并。 合并两个数组O(m + n)的时间复杂度。 因此，对于合并第三个数组，时间复杂度将变为O(m + n + o)。 请注意，这确实是可以解决此问题的最佳时间复杂度。
空间复杂度：由于我们一次合并两个数组，因此我们需要另一个数组来存储第一次合并的结果。 这将空间复杂度提高到O(m + n)。 注意，在计算复杂度时，保留 3 个数组的结果所需的空间将被忽略。
算法：
function merge(A, B)
Let m and n be the sizes of A and B
Let D be the array to store result
// Merge by taking smaller element from A and B
while i < m and j < n
if A[i] <= B[j]
Add A[i] to D and increment i by 1
else Add B[j] to D and increment j by 1
// If array A has exhausted, put elements from B
while j < n
Add B[j] to D and increment j by 1
// If array B has exhausted, put elements from A
while i < n
Add A[j] to D and increment i by 1
Return D
function merge_three(A, B, C)
T = merge(A, B)
return merge(T, C)
具体实现如下：
CPP
// 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 has exhausted
while (i < m)
D.push_back(A[i++]);
// A has exhausted
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 };
// First Merge A and B
Vector T = mergeTwo(A, B);
// Print Result after merging T with C
printVector(mergeTwo(T, C));
return 0;
}
Java
import java.util.*;
// Java program to merge three sorted arrays
// by merging two at a time.
class GFG {
static ArrayList<Integer> mergeTwo(List<Integer> A,
List<Integer> B)
{
// Get sizes of vectors
int m = A.size();
int n = B.size();
// ArrayList for storing Result
ArrayList<Integer> D = new ArrayList<Integer>(m + n);
int i = 0, j = 0;
while (i < m && j < n) {
if (A.get(i) <= B.get(j))
D.add(A.get(i++));
else
D.add(B.get(i++));
}
// B has exhausted
while (i < m)
D.add(A.get(i++));
// A has exhausted
while (j < n)
D.add(B.get(j++));
return D;
}
// Driver code
public static void main(String[] args)
{
Integer[] a = { 1, 2, 3, 5 };
Integer[] b = { 6, 7, 8, 9 };
Integer[] c = { 10, 11, 12 };
List<Integer> A = Arrays.asList(a);
List<Integer> B = Arrays.asList(b);
List<Integer> C = Arrays.asList(c);
// First Merge A and B
ArrayList<Integer> T = mergeTwo(A, B);
// Print Result after merging T with C
System.out.println(mergeTwo(T, C));
}
}
/* This code contributed by PrinciRaj1992 */
Python
# Python program to merge three sorted arrays
# by merging two at a time.
def merge_two(a, b):
(m, n) = (len(a), len(b))
i = j = 0
# Destination Array
d = []
# Merge from a and b together
while i < m and j < n:
if a[i] <= b[j]:
d.append(a[i])
i += 1
else:
d.append(b[j])
j += 1
# Merge from a if b has run out
while i < m:
d.append(a[i])
i += 1
# Merge from b if a has run out
while j < n:
d.append(b[j])
j += 1
return d
def merge(a, b, c):
t = merge_two(a, b)
return merge_two(t, c)
if __name__ == "__main__":
A = [1, 2, 3, 5]
B = [6, 7, 8, 9]
C = [10, 11, 12]
print(merge(A, B, C))
输出：
[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
方法 2（一次三个数组）：
通过将三个数组合并在一起，可以提高方法 1 的空间复杂度。
function merge-three(A, B, C)
Let m, n, o be size of A, B, and C
Let D be the array to store the result
// Merge three arrays at the same time
while i < m and j < n and k < o
Get minimum of A[i], B[j], C[i]
if the minimum is from A, add it to
D and advance i
else if the minimum is from B add it
to D and advance j
else if the minimum is from C add it
to D and advance k
// After above step at least 1 array has
// exhausted. Only C has exhausted
while i < m and j < n
put minimum of A[i] and B[j] into D
Advance i if minimum is from A else advance j
// Only B has exhausted
while i < m and k < o
Put minimum of A[i] and C[k] into D
Advance i if minimum is from A else advance k
// Only A has exhausted
while j < n and k < o
Put minimum of B[j] and C[k] into D
Advance j if minimum is from B else advance k
// After above steps at least 2 arrays have
// exhausted
if A and B have exhausted take elements from C
if B and C have exhausted take elements from A
if A and C have exhausted take elements from B
return D
复杂度：时间复杂度为O(m + n + o)，因为我们一次处理了三个数组中的每个元素。 我们只需要一个数组来存储合并的结果，因此忽略此数组，空间复杂度为O(1)。
该算法的 C++ 和 Python 实现如下所示：
C++
// C++ program to merger 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;
// Get Sizes of three vectors
m = A.size();
n = B.size();
o = C.size();
// Vector for storing output
Vector D;
D.reserve(m + n + o);
i = j = k = 0;
while (i < m && j < n && k < o) {
// Get minimum of a, b, c
int m = min(min(A[i], B[j]), C[k]);
// Put m in D
D.push_back(m);
// Increment i, j, k
if (m == A[i])
i++;
else if (m == B[j])
j++;
else
k++;
}
// C has exhausted
while (i < m && j < n) {
if (A[i] <= B[j]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(B[j]);
j++;
}
}
// B has exhausted
while (i < m && k < 0) {
if (A[i] <= C[j]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(C[j]);
k++;
}
}
// A has exhausted
while (j < n && k < 0) {
if (B[j] <= C[k]) {
D.push_back(B[j]);
j++;
}
else {
D.push_back(C[j]);
k++;
}
}
// A and B have exhausted
while (k < o)
D.push_back(C[k++]);
// B and C have exhausted
while (i < m)
D.push_back(A[i++]);
// A and C have exhausted
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 };
// Print Result
printVector(mergeThree(A, B, C));
return 0;
}
Python
# Python program to merge three sorted arrays
# simultaneously.
def merge_three(a, b, c):
(m, n, o) = (len(a), len(b), len(c))
i = j = k = 0
# Destination array
d = []
while i < m and j < n and k < o:
# Get Minimum element
m = min(a[i], b[j], c[k])
# Add m to D
d.append(m)
# Increment the source pointer which
# gives m
if a[i] == m:
i += 1
elif b[j] == m:
j += 1
elif c[k] == m:
k += 1
# Merge a and b in c has exhausted
while i < m and j < n:
if a[i] <= b[k]:
d.append(a[i])
i += 1
else:
d.append(b[j])
j += 1
# Merge b and c if a has exhausted
while j < n and k < o:
if b[j] <= c[k]:
d.append(b[j])
j += 1
else:
d.append(c[k])
k += 1
# Merge a and c if b has exhausted
while i < m and k < o:
if a[i] <= c[k]:
d.append(a[i])
i += 1
else:
d.append(c[k])
k += 1
# Take elements from a if b and c
# have exhausted
while i < m:
d.append(a[i])
i += 1
# Take elements from b if a and c
# have exhausted
while j < n:
d.append(b[j])
j += 1
# Take elements from c if a and
# b have exhausted
while k < o:
d.append(c[k])
k += 1
return d
if __name__ == "__main__":
a = [1, 2, 41, 52, 84]
b = [1, 2, 41, 52, 67]
c = [1, 2, 41, 52, 67, 85]
print(merge_three(a, b, c))
Java
import java.util.*;
import java.io.*;
import java.lang.*;
class Sorting {
public static void main(String[] args)
{
int A[] = { 1, 2, 41, 52, 84 };
int B[] = { 1, 2, 41, 52, 67 };
int C[] = { 1, 2, 41, 52, 67, 85 };
// call the function to sort and print the sorted numbers
merge3sorted(A, B, C);
}
// Function to merge three sorted arrays
// A[], B[], C[]: input arrays
static void merge3sorted(int A[], int B[], int C[])
{
// creating an empty list to store sorted numbers
ArrayList<Integer> list = new ArrayList<Integer>();
int i = 0, j = 0, k = 0;
// using merge concept and trying to find
// smallest of three while all three arrays
// contains at least one element
while (i < A.length && j < B.length && k < C.length) {
int a = A[i];
int b = B[j];
int c = C[k];
if (a <= b && a <= c) {
list.add(a);
i++;
}
else if (b <= a && b <= c) {
list.add(b);
j++;
}
else {
list.add(c);
k++;
}
}
// next three while loop is to sort two
// of arrays if one of the three gets exhausted
while (i < A.length && j < B.length) {
if (A[i] < B[j]) {
list.add(A[i]);
i++;
}
else {
list.add(B[j]);
j++;
}
}
while (j < B.length && k < C.length) {
if (B[j] < C[k]) {
list.add(B[j]);
j++;
}
else {
list.add(C[k]);
k++;
}
}
while (i < A.length && k < C.length) {
if (A[i] < C[k]) {
list.add(A[i]);
i++;
}
else {
list.add(C[k]);
k++;
}
}
// if one of the array are left then
// simply appending them as there will
// be only largest element left
while (i < A.length) {
list.add(A[i]);
i++;
}
while (j < B.length) {
list.add(B[j]);
j++;
}
while (k < C.length) {
list.add(C[k]);
k++;
}
// finally print the list
for (Integer x : list)
System.out.print(x + " ");
} // merge3sorted closing braces
}
Output
[1, 1, 1, 2, 2, 2, 41, 41, 41, 52, 52, 52, 67, 67, 84, 85]
注意：虽然实现直接过程来合并两个或三个数组比较容易，但是如果我们要合并 4 个或更多数组，则过程变得很麻烦。 在这种情况下，我们应遵循合并K个排序数组中所示的过程。
版权属于：月萌API www.moonapi.com，转载请注明出处
