algorithm - suma - Encuentra la mediana de un flujo de enteros
diagrama de flujo y pseudocodigo que determina tu edad (4)
Dada una secuencia sin clasificar de números enteros que fluye en su programa como una secuencia.
Los enteros son demasiados para caber en la memoria.
Imagina que hay una función:
int getNext() throws NoSuchElementException;
Devuelve el siguiente entero de la secuencia.
Escribe una función para encontrar la mediana.
Resuelve el problema en O (n).
¿Algunas ideas?
Se da una sugerencia (use la estructura de datos de pila ..)
Debe mantener dos pilas: una pila máxima (que contiene los elementos N / 2 más pequeños vistos hasta ahora) y una pila mínima (que contiene los elementos N / 2 más grandes). Almacena el elemento extra a un lado si N es impar.
Siempre que llame a la función getNext (),
Si N se vuelve impar, guarde el nuevo elemento como el elemento extra. Si es necesario, intercambie ese elemento con uno del min-heap o max-heap para satisfacer la siguiente condición
max (max-heap) <= elemento extra <= min (min-heap).
Si N se iguala, haz lo mismo que arriba para obtener un segundo elemento extra. Luego, agregue el más pequeño al max-heap y el más grande al min-heap. El inserto debe ser O (registro N)
Obtener Mediana: O (1)
Si N es impar, la mediana es el elemento extra.
Si N es par, la mediana es el promedio entre las cimas de los 2 montones
Supongamos que la ventana para que se mantenga la mediana es K. Construya un árbol de búsqueda binario para el número K. DE ACUERDO); Haga el recorrido en orden y encuentre el (K / 2) elemento th.O (K / 2);
El tiempo total es O (K).
Usando un algoritmo de selección, podemos lograr esto en O (n) complejidad. Pero todavía no entiendo claramente el uso de un montón en este caso.
Vea este paper . Tomará (probablemente) más de un pase. La idea es que en cada paso los límites superior e inferior se calculan de tal manera que la mediana se encuentra entre ellos.
Un resultado fundamental aquí es N = tamaño de los datos, P = número de pases
Teorema 2) Un algoritmo de paso P que selecciona el Kº más alto de N elementos requiere almacenamiento a lo sumo O (N ( 1 / P ) (registro N) (2- 2 / P ) ) .
Además, para cantidades muy pequeñas de almacenamiento S , es decir, para 2 <= S <= O ((log N) 2 ) , hay una clase de algoritmos de selección que utilizan a lo sumo O ((log N) 3 / S ) pases .
Lee el papel. No estoy realmente seguro de lo que el montón tiene que ver con eso