合并 3 個排序的數組 · GeeksForGeeks 中文系列教程

# 合并 3 個排序的數組 > 原文： [https://www.geeksforgeeks.org/merge-3-sorted-arrays/](https://www.geeksforgeeks.org/merge-3-sorted-arrays/) 給定 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 個排序的數組](https://www.geeksforgeeks.org/merge-two-sorted-arrays/)。因此，我們可以首先合并兩個數組，然后將結果與第三個數組合并。合并兩個數組 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 ```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++ ```cpp // 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 ```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 個排序數組](https://www.geeksforgeeks.org/merge-k-sorted-arrays/)中所示的過程。 * * * * * *