Dada una array arr[] de tamaño N que representa los enteros necesarios para leerse como un flujo de datos, la tarea es calcular e imprimir la mediana después de leer cada entero.
Ejemplos:
Entrada: arr[] = { 5, 10, 15 }
Salida: 5 7.5 10
Explicación:
Después de leer arr[0] del flujo de datos, la mediana es 5.
Después de leer arr[1] del flujo de datos, la mediana es 7.5.
Después de leer arr[2] del flujo de datos, la mediana es 10.Entrada: arr[] = { 1, 2, 3, 4 }
Salida: 1 1.5 2 2.5
Enfoque: El problema se puede resolver usando el Conjunto Ordenado . Siga los pasos a continuación para resolver el problema:
- Inicialice un conjunto ordenado múltiple, por ejemplo, mst para almacenar los elementos de la array en un orden ordenado.
- Recorre la array usando la variable i . Para cada i -ésimo elemento, inserte arr[i] en mst y verifique si la variable i es par o no . Si se encuentra que es cierto, imprima la mediana usando (*mst.find_by_order(i / 2)) .
- De lo contrario, imprima la mediana tomando el promedio de (*mst.find_by_order(i / 2)) y (*mst.find_by_order((i + 1) / 2)) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type,
less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> idxmst;
// Function to find the median
// of running integers
void findMedian(int arr[], int N)
{
// Initialise a multi ordered set
// to store the array elements
// in sorted order
idxmst mst;
// Traverse the array
for (int i = 0; i < N; i++) {
// Insert arr[i] into mst
mst.insert(arr[i]);
// If i is an odd number
if (i % 2 != 0) {
// Stores the first middle
// element of mst
double res
= *mst.find_by_order(i / 2);
// Stores the second middle
// element of mst
double res1
= *mst.find_by_order(
(i + 1) / 2);
cout<< (res + res1) / 2.0<<" ";
}
else {
// Stores middle element of mst
double res
= *mst.find_by_order(i / 2);
// Print median
cout << res << " ";
}
}
}
// Driver Code
int main()
{
// Given stream of integers
int arr[] = { 1, 2, 3, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
findMedian(arr, N);
}
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por debojyoti7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA