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