La mediana es el valor medio en una lista de números enteros ordenados. Si el tamaño de la lista es par, no hay un valor medio. Entonces, la mediana es la media de los dos valores medios.
Análisis
En primer lugar, parece que la mejor complejidad de tiempo que podemos obtener para este problema es O (log (n)) de add () y O (1) de getMedian (). Es muy probable que esta estructura de datos sea un árbol.
Podemos usar heap para resolver este problema. En Java, el PriorityQueue la clase es un montón de prioridad. Podemos usar dos montones para almacenar la mitad inferior y la mitad superior del flujo de datos. El tamaño de los dos montones difiere como máximo 1.
class MedianFinder { PriorityQueue<Integer> minHeap = null; PriorityQueue<Integer> maxHeap = null; /** initialize your data structure here. */ public MedianFinder() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); } public void addNum(int num) { minHeap.offer(num); maxHeap.offer(minHeap.poll()); if(minHeap.size()<maxHeap.size()){ minHeap.offer(maxHeap.poll()); } } public double findMedian() { if(minHeap.size() > maxHeap.size()){ return minHeap.peek(); }else { return (minHeap.peek()+maxHeap.peek())/2.0; } } } |
