Esta es una pregunta común en las entrevistas. Tiene un flujo de números que ingresan (digamos más de un millón). Los números están entre [0-999]).
Implement a class which supports three methods in O(1) * insert(int i); * getMean(); * getMedian();Este es mi código.
public class FindAverage { private int[] store; private long size; private long total; private int highestIndex; private int lowestIndex; public FindAverage() { store = new int[1000]; size = 0; total = 0; highestIndex = Integer.MIN_VALUE; lowestIndex = Integer.MAX_VALUE; } public void insert(int item) throws OutOfRangeException { if(item < 0 || item > 999){ throw new OutOfRangeException(); } store[item] ++; size ++; total += item; highestIndex = Integer.max(highestIndex, item); lowestIndex = Integer.min(lowestIndex, item); } public float getMean(){ return (float)total/size; } public float getMedian(){ } }Parece que no puedo pensar en una manera de obtener la mediana en tiempo O (1). Cualquier ayuda apreciada.
Ya ha hecho todo el trabajo pesado construyendo los mostradores de las store . Junto con el valor del size , es bastante fácil.
Simplemente comience a iterar la store , sumando los conteos hasta llegar a la mitad del size . Ese es su valor medio, si el size es impar. Para un size uniforme, tomará los dos valores circundantes y obtendrá su promedio.
El rendimiento es O(1000/2) en promedio, lo que significa O(1) , ya que no depende de n , es decir, el rendimiento no cambia incluso si n alcanza los miles de millones.
Recuerde, O(1) no significa instantáneo, ni siquiera rápido. Como dice Wikipedia :
Se dice que un algoritmo es de tiempo constante (también escrito como O(1) tiempo) si el valor de T(n) está limitado por un valor que no depende del tamaño de la entrada .
En su caso, ese límite es 1000.
Los posibles valores que puede leer son bastante limitados, solo 1000. Por lo tanto, puede pensar en implementar algo como una clasificación de conteo : cada vez que se ingresa un número, aumenta el contador para ese valor.
Para implementar la mediana en tiempo constante, necesitará dos números: el índice de la mediana (es decir, el valor de la mediana) y la cantidad de valores que ha leído y que están a la izquierda (o derecha) de la mediana. Me detendré aquí con la esperanza de que puedas descubrir cómo continuar por tu cuenta.
EDITAR (como se indica en los comentarios): ya tiene la matriz con los elementos ordenados ( stored ) y conoce la cantidad de elementos a la izquierda de la mediana ( size/2 ). Solo necesita unir la lógica. Me gustaría señalar que si usa memoria adicional lineal, no necesitará iterar sobre toda la matriz en cada inserción.
Para el caso general , donde el rango de elementos es ilimitado, dicha estructura de datos no existe en base a ningún algoritmo basado en comparaciones, ya que permitirá la clasificación O(n) .
Prueba: suponga que tal DS existe, sea D .
Sea A una matriz de entrada para ordenar. (Suponga que A.size() es incluso por simplicidad, que se puede relajar con bastante facilidad agregando un elemento basura y descartándolo más tarde).
sort(A): ds = new D() for each x in A: ds.add(x) m1 = min(A) - 1 m2 = max(A) + 1 for (i=0; i < A.size(); i++): ds.add(m1) # at this point, ds.median() is smallest element in A for (i = 0; i < A.size(); i++): yield ds.median() # Each two insertions advances median by 1 ds.add(m2) ds.add(m2) Afirmación 1: este algoritmo se ejecuta en O(n) .
Prueba: dado que tenemos operaciones constantes de add() y mediana(), cada una de ellas es O(1) por iteración, y el número de iteraciones es lineal; la complejidad es lineal.
Afirmación 2: La salida está ordenada (A).
Prueba (directrices): Después de insertar n veces m1 , la mediana es el elemento más pequeño en A Cada dos inserciones posteriores avanza la mediana en un elemento, y dado que se ordena el avance, se ordena la salida total.
Dado que el algoritmo anterior ordena en O(n) , y no es posible bajo el modelo de comparación, tal DS no existe.
QED.