Dadas dos arrays ordenadas, debemos fusionarlas con O(1) espacio adicional en una array ordenada, cuando N es el tamaño de la primera array y M es el tamaño de la segunda array.
Ejemplo :
Input: arr1[] = {10}; arr2[] = {2, 3}; Output: arr1[] = {2} arr2[] = {3, 10} Input: arr1[] = {1, 5, 9, 10, 15, 20}; arr2[] = {2, 3, 8, 13}; Output: arr1[] = {1, 2, 3, 5, 8, 9} arr2[] = {10, 13, 15, 20}
Ya habíamos discutido dos enfoques más para resolver el problema anterior en el espacio constante:
- Combine dos arrays ordenadas con O (1) espacio adicional .
- Fusión eficiente de dos arrays ordenadas con O (1) espacio adicional .
En este artículo, se analiza un enfoque más que utiliza el concepto de la estructura de datos del montón sin ocupar espacio adicional para fusionar las dos arrays ordenadas.
A continuación se muestra el enfoque detallado en pasos:
- La idea es convertir primero la segunda array en un montón mínimo. Esto se puede hacer en complejidad de tiempo O(M).
- Después de convertir la segunda array a min-heap:
- Comience a recorrer la primera array y compare el elemento actual de la primera array con la parte superior del min_heap creado.
- Si el elemento actual en la primera array es mayor que la parte superior del montón, intercambie el elemento actual de la primera array con la raíz del montón y apile la raíz del min_heap.
- Después de realizar la operación anterior para cada elemento de la primera array, la primera array ahora contendrá los primeros N elementos de la array combinada ordenada.
- Ahora, los elementos que quedaron en min_heap o en la segunda array son los últimos M elementos de la array combinada ordenada.
- Para organizarlos en orden, aplique heapsort en el lugar en la segunda array.
Nota : hemos utilizado funciones STL integradas disponibles en C++ para convertir la array en min_heap, ordenar el montón, etc. Se recomienda leer – Montón en C++ STL | make_heap(), push_heap(), pop_heap(), sort_heap() antes de pasar al programa.
A continuación se muestra la implementación del enfoque anterior:
// C++ program to merge two sorted arrays in // constant space #include <bits/stdc++.h> using namespace std; // Function to merge two sorted arrays in // constant space void mergeArrays(int* a, int n, int* b, int m) { // Convert second array into a min_heap // using make_heap() STL function [takes O(m)] make_heap(b, b + m, greater<int>()); // Start traversing the first array for (int i = 0; i < n; i++) { // If current element is greater than root // of min_heap if (a[i] > b[0]) { // Pop minimum element from min_heap using // pop_heap() STL function // The pop_heap() function removes the minimum element from // heap and moves it to the end of the container // converted to heap and reduces heap size by 1 pop_heap(b, b + m, greater<int>()); // Swapping the elements int tmp = a[i]; a[i] = b[m - 1]; b[m - 1] = tmp; // Apply push_heap() function on the container // or array to again reorder it in the // form of min_heap push_heap(b, b + m, greater<int>()); } } // Convert the second array again into max_heap // because sort_heap() on min heap sorts the array // in decreasing order // This step is [O(m)] make_heap(b, b + m); // It's a max_heap // Sort the second array using sort_heap() function sort_heap(b, b + m); } // Driver Code int main() { int ar1[] = { 1, 5, 9, 10, 15, 20 }; int ar2[] = { 2, 3, 8, 13 }; int m = sizeof(ar1) / sizeof(ar1[0]); int n = sizeof(ar2) / sizeof(ar2[0]); mergeArrays(ar1, m, ar2, n); cout << "After Merging :- \nFirst Array: "; for (int i = 0; i < m; i++) cout << ar1[i] << " "; cout << "\nSecond Array: "; for (int i = 0; i < n; i++) cout << ar2[i] << " "; return 0; }
After Merging :- First Array: 1 2 3 5 8 9 Second Array: 10 13 15 20
Complejidad de tiempo : O(N*logM + M*logN)
Espacio auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA