Dado que los enteros se leen de un flujo de datos. Encuentre la mediana de todos los elementos leídos hasta ahora a partir del primer entero hasta el último entero. Esto también se llama Mediana de enteros móviles.
El enlace dado ya contiene la solución de este problema usando Priority Queue .
Sin embargo, la siguiente solución utiliza el mismo concepto, pero la implementación se realiza mediante el uso de conjuntos.
En esta solución, imprimiremos la mediana más pequeña en caso de longitud uniforme en lugar de tomar su promedio.
Ejemplos:
Entrada: arr[] = {-10, 14, 11, -5, 7}
Salida: -10 -10 11 -5 7Entrada: arr[] = {2, -5, 14}
Salida: 2 -5 2
Acercarse:
- Cree dos conjuntos múltiples g en orden ascendente que almacenarán la mitad superior y s en orden descendente para almacenar la mitad inferior de la array arr[] .
- Inserte el primer elemento en s . E inicializa la mediana con este valor.
- Para cualquier otro elemento de la array x . Consulta las tallas de ambos conjuntos:
- Cuando tamaño(s) > tamaño(g) : si x > mediana , inserte el primer elemento de s en g y elimine ese elemento de s , inserte x en s . De lo contrario, inserte x en g .
- Cuando tamaño(s) < tamaño(g) : Si x < mediana , inserte el primer elemento de g en s y elimine ese elemento de g , inserte x en g . De lo contrario, inserte x en s .
- Cuando talla(s) = talla(g) : Si x > mediana . Inserta x en s . De lo contrario, inserte x en g .
A continuación se muestra la implementación del enfoque anterior:
// C++ program to find running median for
// a stream of integers using Set
#include <bits/stdc++.h>
using namespace std;
// Function to print the running median
// for the array arr[]
void printRunningMedian(int arr[], int n)
{
// Multiset is used to handle duplicates
// Multiset g for storing upper half
// (ascending order)
// The first element will be the smallest)
multiset<int> g;
// Multiset s for storing lower half
// (descending order). The first element
// will be the largest
multiset<int, greater<int> > s;
s.insert(arr[0]);
// Initialise median with the first element
int med = arr[0];
printf("%d ", med);
for (int i = 1; i < n; i++) {
// Only add elements to upper half if
// its size less then the size of the
// lower half (maintain only difference
// of 1)
if (s.size() > g.size()) {
if (arr[i] < med) {
int temp = *s.begin();
s.erase(s.begin());
g.insert(temp);
s.insert(arr[i]);
}
else
g.insert(arr[i]);
med = *s.begin() > *g.begin() ?
*g.begin() : *s.begin();
}
// Only add elements to lower half if
// it's size less then the size of the
// upper half (maintain only difference
// of 1)
else if (s.size() < g.size()) {
if (arr[i] > med) {
int temp = *g.begin();
g.erase(g.begin());
s.insert(temp);
g.insert(arr[i]);
}
else
s.insert(arr[i]);
med = *s.begin() > *g.begin() ?
*g.begin() : *s.begin();
}
// If sizes are same
else {
if (arr[i] > med) {
g.insert(arr[i]);
med = *g.begin();
}
else {
s.insert(arr[i]);
med = *s.begin();
}
}
printf("%d ", med);
}
printf("\n");
}
// Driver code
int main()
{
int arr[] = { -10, 14, 11, -5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
printRunningMedian(arr, n);
return 0;
}
-10 -10 11 -5 7
Publicación traducida automáticamente
Artículo escrito por Praveen Sinha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA