Dadas dos arrays ordenadas , arr[] , brr[] de tamaño N y M , la tarea es fusionar las dos arrays dadas de modo que formen una secuencia ordenada de enteros que combinen elementos de ambas arrays.
Ejemplos:
Entrada: arr[] = {10}, brr[] = {2, 3}
Salida : 2 3 10
Explicación: La array ordenada combinada obtenida al tomar todos los elementos de ambas arrays es {2, 3, 10}.
Por lo tanto, la salida requerida es 2 3 10.Entrada: arr[]= {1, 5, 9, 10, 15, 20}, brr[] = {2, 3, 8, 13}
Salida: 1 2 3 5 8 9 10 13 15 20
Enfoque ingenuo: Consulte Fusionar dos arrays ordenadas para obtener el enfoque más simple para fusionar las dos arrays dadas.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Enfoque optimizado para el espacio: Consulte Fusionar dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Enfoque de optimización de espacio eficiente: consulte Fusionar de manera eficiente dos arrays ordenadas con O(1) espacio adicional para fusionar las dos arrays dadas sin usar memoria adicional.
Complejidad de tiempo: O((N + M) * log(N + M))
Espacio auxiliar: O(1)
Enfoque basado en montón : el problema se puede resolver usando Heap . La idea es recorrer la array arr[] y comparar el valor de arr[i] con brr[0] y verificar si arr[i] es mayor que brr[0] o no. Si se determina que es cierto, entonces swap(arr[i], brr[0) y realice laoperación heapify en brr[] . Siga los pasos a continuación para resolver el problema:
- Recorra la array arr[] y compare el valor de arr[i] con brr[0] y verifique si arr[i] es mayor que brr[0] o no. Si se determina que es cierto, entonces swap(arr[i], brr[0) y realice la operación heapify en brr[] .
- Finalmente, ordene la array brr[] e imprima ambas arrays.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform min heapify
// on array brr[]
void minHeapify(int brr[], int i, int M)
{
// Stores index of left child
// of i.
int left = 2 * i + 1;
// Stores index of right child
// of i.
int right = 2 * i + 2;
// Stores index of the smallest element
// in (arr[i], arr[left], arr[right])
int smallest = i;
// Check if arr[left] less than
// arr[smallest]
if (left < M && brr[left] < brr[smallest]) {
// Update smallest
smallest = left;
}
// Check if arr[right] less than
// arr[smallest]
if (right < M && brr[right] < brr[smallest]) {
// Update smallest
smallest = right;
}
// if i is not the index
// of smallest element
if (smallest != i) {
// Swap arr[i] and arr[smallest]
swap(brr[i], brr[smallest]);
// Perform heapify on smallest
minHeapify(brr, smallest, M);
}
}
// Function to merge two sorted arrays
void merge(int arr[], int brr[],
int N, int M)
{
// Traverse the array arr[]
for (int i = 0; i < N; ++i) {
// Check if current element
// is less than brr[0]
if (arr[i] > brr[0]) {
// Swap arr[i] and brr[0]
swap(arr[i], brr[0]);
// Perform heapify on brr[]
minHeapify(brr, 0, M);
}
}
// Sort array brr[]
sort(brr, brr + M);
}
// Function to print array elements
void printArray(int arr[], int N)
{
// Traverse array arr[]
for (int i = 0; i < N; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 2, 23, 35, 235, 2335 };
int brr[] = { 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = sizeof(brr) / sizeof(brr[0]);
// Function call to merge
// two array
merge(arr, brr, N, M);
// Print first array
printArray(arr, N);
// Print Second array.
printArray(brr, M);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to perform
// min heapify on array
// brr[]
static void minHeapify(int brr[],
int i, int M)
{
// Stores index of left
// child of i.
int left = 2 * i + 1;
// Stores index of right
// child of i.
int right = 2 * i + 2;
// Stores index of the smallest
// element in (arr[i], arr[left],
// arr[right])
int smallest = i;
// Check if arr[left] less than
// arr[smallest]
if (left < M && brr[left] <
brr[smallest])
{
// Update smallest
smallest = left;
}
// Check if arr[right] less
// than arr[smallest]
if (right < M && brr[right] <
brr[smallest])
{
// Update smallest
smallest = right;
}
// if i is not the index
// of smallest element
if (smallest != i)
{
// Swap arr[i] and
// arr[smallest]
int temp = brr[i];
brr[i] = brr[smallest];
brr[smallest] = temp;
// Perform heapify on smallest
minHeapify(brr, smallest, M);
}
}
// Function to merge two
// sorted arrays
static void merge(int arr[], int brr[],
int N, int M)
{
// Traverse the array arr[]
for (int i = 0; i < N; ++i)
{
// Check if current element
// is less than brr[0]
if (arr[i] > brr[0])
{
// Swap arr[i] and brr[0]
int temp = arr[i];
arr[i] = brr[0];
brr[0] = temp;
// Perform heapify on brr[]
minHeapify(brr, 0, M);
}
}
// Sort array brr[]
Arrays.sort(brr);
}
// Function to print array
// elements
static void printArray(int arr[],
int N)
{
// Traverse array arr[]
for (int i = 0; i < N; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {2, 23, 35, 235, 2335};
int brr[] = {3, 5};
int N = arr.length;
int M = brr.length;
// Function call to merge
// two array
merge(arr, brr, N, M);
// Print first array
printArray(arr, N);
// Print Second array.
printArray(brr, M);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach # Function to perform min heapify # on array brr[] def minHeapify(brr, i, M): # Stores index of left child # of i. left = 2 * i + 1 # Stores index of right child # of i. right = 2 * i + 2 # Stores index of the smallest element # in (arr[i], arr[left], arr[right]) smallest = i # Check if arr[left] less than # arr[smallest] if (left < M and brr[left] < brr[smallest]): # Update smallest smallest = left # Check if arr[right] less than # arr[smallest] if (right < M and brr[right] < brr[smallest]): # Update smallest smallest = right # If i is not the index # of smallest element if (smallest != i): # Swap arr[i] and arr[smallest] brr[i], brr[smallest] = brr[smallest], brr[i] # Perform heapify on smallest minHeapify(brr, smallest, M) # Function to merge two sorted arrays def merge(arr, brr, N, M): # Traverse the array arr[] for i in range(N): # Check if current element # is less than brr[0] if (arr[i] > brr[0]): # Swap arr[i] and brr[0] arr[i], brr[0] = brr[0], arr[i] # Perform heapify on brr[] minHeapify(brr, 0, M) # Sort array brr[] brr.sort() # Function to print array elements def printArray(arr, N): # Traverse array arr[] for i in range(N): print(arr[i], end = " ") # Driver code if __name__ == '__main__': arr = [ 2, 23, 35, 235, 2335 ] brr = [3, 5] N = len(arr) M = len(brr) # Function call to merge # two array merge(arr, brr, N, M) # Print first array printArray(arr, N) # Print Second array. printArray(brr, M) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to perform
// min heapify on array
// brr[]
static void minHeapify(int []brr,
int i, int M)
{
// Stores index of left
// child of i.
int left = 2 * i + 1;
// Stores index of right
// child of i.
int right = 2 * i + 2;
// Stores index of the smallest
// element in (arr[i], arr[left],
// arr[right])
int smallest = i;
// Check if arr[left] less than
// arr[smallest]
if (left < M && brr[left] <
brr[smallest])
{
// Update smallest
smallest = left;
}
// Check if arr[right] less
// than arr[smallest]
if (right < M && brr[right] <
brr[smallest])
{
// Update smallest
smallest = right;
}
// If i is not the index
// of smallest element
if (smallest != i)
{
// Swap arr[i] and
// arr[smallest]
int temp = brr[i];
brr[i] = brr[smallest];
brr[smallest] = temp;
// Perform heapify on smallest
minHeapify(brr, smallest, M);
}
}
// Function to merge two
// sorted arrays
static void merge(int []arr, int[]brr,
int N, int M)
{
// Traverse the array []arr
for(int i = 0; i < N; ++i)
{
// Check if current element
// is less than brr[0]
if (arr[i] > brr[0])
{
// Swap arr[i] and brr[0]
int temp = arr[i];
arr[i] = brr[0];
brr[0] = temp;
// Perform heapify on brr[]
minHeapify(brr, 0, M);
}
}
// Sort array brr[]
Array.Sort(brr);
}
// Function to print array
// elements
static void printArray(int []arr,
int N)
{
// Traverse array []arr
for(int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 23, 35, 235, 2335 };
int []brr = {3, 5};
int N = arr.Length;
int M = brr.Length;
// Function call to merge
// two array
merge(arr, brr, N, M);
// Print first array
printArray(arr, N);
// Print Second array.
printArray(brr, M);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to perform min heapify
// on array brr[]
function minHeapify(brr, i, M)
{
// Stores index of left child
// of i.
let left = 2 * i + 1;
// Stores index of right child
// of i.
let right = 2 * i + 2;
// Stores index of the smallest element
// in (arr[i], arr[left], arr[right])
let smallest = i;
// Check if arr[left] less than
// arr[smallest]
if (left < M && brr[left] < brr[smallest]) {
// Update smallest
smallest = left;
}
// Check if arr[right] less than
// arr[smallest]
if (right < M && brr[right] < brr[smallest]) {
// Update smallest
smallest = right;
}
// if i is not the index
// of smallest element
if (smallest != i) {
// Swap arr[i] and arr[smallest]
let temp = brr[i];
brr[i] = brr[smallest];
brr[smallest] = temp;
// Perform heapify on smallest
minHeapify(brr, smallest, M);
}
}
// Function to merge two sorted arrays
function merge(arr, brr,
N, M)
{
// Traverse the array arr[]
for (let i = 0; i < N; ++i) {
// Check if current element
// is less than brr[0]
if (arr[i] > brr[0]) {
// Swap arr[i] and brr[0]
let temp = arr[i];
arr[i] = brr[0];
brr[0] = temp;
// Perform heapify on brr[]
minHeapify(brr, 0, M);
}
}
// Sort array brr[]
brr.sort();
}
// Function to print array elements
function printArray(arr, N)
{
// Traverse array arr[]
for (let i = 0; i < N; i++)
document.write(arr[i] + " ");
}
// Driver Code
let arr = [ 2, 23, 35, 235, 2335 ];
let brr = [ 3, 5 ];
let N = arr.length;
let M = brr.length;
// Function call to merge
// two array
merge(arr, brr, N, M);
// Print first array
printArray(arr, N);
// Print Second array.
printArray(brr, M);
//This code is contributed by Mayank Tyagi
</script>
Producción:
2 3 5 23 35 235 2335
Complejidad de tiempo: O((N + M) * log (M))
Espacio auxiliar: O(1)
Enfoque eficiente: Consulte fusionar dos arrays ordenadas para fusionar de manera eficiente las dos arrays dadas.
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)