给定3个按升序排序的数组（A、B、C），我们需要按升序将它们合并在一起并输出数组D。
null
例如：
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 Dfunction 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 has exhausted while (i < m) D.push_back(A[i++]); // A has exhausted while (j < n) D.push_back(B[j++]); return D; } // Driver Code 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(j++)); } // 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)) |
Javascript
<script> // Javascript program to merge three sorted arrays // by merging two at a time. function mergeTwo(A, B) { // Get sizes of vectors let m = A.length; let n = B.length; // Vector for storing Result let D = []; let i = 0, j = 0; while (i < m && j < n) { if (A[i] <= B[j]) D.push(A[i++]); else D.push(B[j++]); } // B has exhausted while (i < m) D.push(A[i++]); // A has exhausted while (j < n) D.push(B[j++]); return D; } // Driver Code let A = [ 1, 2, 3, 5 ]; let B = [ 6, 7, 8, 9 ]; let C = [ 10, 11, 12 ]; // First Merge A and B let T = mergeTwo(A, B); // Print Result after merging T with C document.write(mergeTwo(T, C)); </script> |
输出：
[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++
// 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 < o) { if (A[i] <= C[k]) { D.push_back(A[i]); i++; } else { D.push_back(C[k]); k++; } } // A has exhausted while (j < n && k < o) { if (B[j] <= C[k]) { D.push_back(B[j]); j++; } else { D.push_back(C[k]); 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; } // Driver Code 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; } |
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 } |
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)) |
Javascript
<script> // Javascript program to merger three sorted arrays // by merging three simultaneously. function printVector(a) { document.write( "[" ); for (let e of a) { document.write(e + " " ); } document.write( "]" + "<br>" ); } function mergeThree(A, B, C) { let m, n, o, i, j, k; // Get Sizes of three vectors m = A.length; n = B.length; o = C.length; // Vector for storing output let D = []; i = j = k = 0; while (i < m && j < n && k < o) { // Get minimum of a, b, c let m = Math.min(Math.min(A[i], B[j]), C[k]); // Put m in D D.push(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(A[i]); i++; } else { D.push(B[j]); j++; } } // B has exhausted while (i < m && k < o) { if (A[i] <= C[k]) { D.push(A[i]); i++; } else { D.push(C[k]); k++; } } // A has exhausted while (j < n && k < o) { if (B[j] <= C[k]) { D.push(B[j]); j++; } else { D.push(C[k]); k++; } } // A and B have exhausted while (k < o) D.push(C[k++]); // B and C have exhausted while (i < m) D.push(A[i++]); // A and C have exhausted while (j < n) D.push(B[j++]); return D; } // Driver Code let A = [1, 2, 41, 52, 84]; let B = [1, 2, 41, 52, 67]; let C = [1, 2, 41, 52, 67, 85]; // Print Result printVector(mergeThree(A, B, C)); // This code is contributed by gfgking. </script> |
输出
[1 1 1 2 2 2 41 41 41 52 52 52 67 67 84 85 ]
注： 虽然实现合并两个或三个数组的直接过程相对容易，但如果要合并4个或更多数组，该过程会变得很麻烦。在这种情况下，我们应该遵循中所示的程序 合并K排序数组 .
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
