Hacer un seguimiento de la mediana de una expansión de gama

Question

Pregunta De la Entrevista:

Editado A continuación Se le da una matriz. Usted hace 2 montones de él, un minheap y el otro montón máximo. Ahora encuentre la mediana de la matriz usando estos 2 montones proporcionados en el tiempo O (nlog n).

Pregunta corregida Los números se generan aleatoriamente y se almacenan en una matriz (en expansión). ¿Cómo harías un seguimiento de la mediana?

Solución Este problema se puede resolver usando 2 pilas y siempre se puede acceder a la mediana en O (1) vez.

Answer 1

Saltar desde un montón es una operación O (log N), por lo que puede lograr O (N log N) sacando la mitad de los elementos de uno de los montones y tomando el último valor reventado (tendría que manejar cajas de borde). Sin embargo, esto no aprovecha el otro montón.

Puede lograr O (N) con el selection algorithm, pero el factor constante es muy alto. La sugerencia anterior es probablemente mejor si ya tiene un montón.

Answer 2

Así es como usa ambos montones. Tenga en cuenta que asumo que no conoce la cantidad de elementos, y esta es la razón por la que debemos abrir hasta que saquemos algo del montón mínimo que sea mayor o igual que lo que sacamos del montón máximo. Tenga en cuenta que devolvemos el promedio porque en el caso de un conjunto como {1, 2, 3, 4}, la mediana es en realidad 2.5 (el promedio de los dos valores "medios"). Supongo que double es el tipo de valor, pero obviamente puede ser cualquier cosa. Aquí:

double min = minheap.pop(); 
double max = maxheap.pop(); 
while(min < max) { 
    min = minheap.pop(); 
    max = maxheap.pop(); 
} 

return (min + max)/2; 

Desde hace estallar es O(log n) y tenemos que hacer estallar O(n/2) valores, esto es O(n log n).

Answer 3

Una implementación de trabajo en java, usando 2 montones, O (n log n). En cualquier momento, mantengo los dos montones equilibrados en tamaño (es decir, difieren a lo sumo en 1, si ingresamos n elementos tales que n% 2 == 1). Obtener la mediana es O (1). Agregar un nuevo elemento es O (log n).

public class MedianOfStream { 

    private int count; 
    private PriorityQueue<Integer> highs, lows; 

    public MedianOfStream() { 
     highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() { 
      @Override 
      public int compare(Integer arg0, Integer arg1) { 
       return arg0.compareTo(arg1); 
      } 
     }); 
     lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() { 
      @Override 
      public int compare(Integer arg0, Integer arg1) { 
       return arg1.compareTo(arg0); 
      } 
     }); 
    } 

    private int getMedian() { 
     if (count == 0) 
      return 0; 
     if (lows.size() == highs.size()) { 
      return (lows.peek() + highs.peek())/2; 
     } else if (lows.size() < highs.size()) { 
      return highs.peek(); 
     } 
     return lows.peek(); 
    } 

    private void swap(){ 
     int h = highs.poll(); 
     int l = lows.poll(); 
     highs.add(l); 
     lows.add(h); 
    } 

    public int updateMedian(int n) { 
     count++; 

     if (count == 1) 
      lows.add(n); 

     else if (count==2) { 
      highs.add(n); 
      if(highs.peek()<lows.peek()) { 
       swap(); // O(log n) 
      } 
     } 

     else { 
      if (n > highs.peek()) { 
       lows.add(highs.poll()); // O(log n) 
       highs.add(n); // O(log n) 
      } else { 
       highs.add(lows.poll()); // O(log n) 
       lows.add(n); // O(log n) 
      } 
      if(highs.peek()<lows.peek()) { 
       swap(); // O(log n) 
      } 
     } 

     // if we added an even # of items, 
     // the heaps must be exactly the same size, 
     // otherwise we tolerate a 1-off difference 

     if (Math.abs(lows.size() - highs.size()) > (count % 2)) { 
      if (lows.size() < highs.size()) { 
       lows.add(highs.poll()); // O(log n) 
      } else { 
       highs.add(lows.poll()); // O(log n) 
      } 
     } 

     return getMedian(); // O(1) 
    } 
} 

Answer 4

solución de JavaScript utilizando dos montones:

function addNewNumber(minHeap, maxHeap, randomNumber) { 
    if (maxHeap.size() === minHeap.size()) { 
    if (minHeap.peek() && randomNumber > minHeap.peek()) { 
     maxHeap.insert(minHeap.remove()); 
     minHeap.insert(randomNumber); 
    } else { 
     maxHeap.insert(randomNumber); 
    } 
    } else { 
    if (randomNumber < maxHeap.peek()) { 
     minHeap.insert(maxHeap.remove()); 
     maxHeap.insert(randomNumber); 
    } else { 
     minHeap.insert(randomNumber); 
    } 
    } 
} 

function getMedian(minHeap, maxHeap) { 
    if (!maxHeap.size()) { 
    return 0; 
    } 
    if (minHeap.size() === maxHeap.size()) { 
    return (minHeap.peek() + maxHeap.peek())/2; 
    } else { 
    return maxHeap.peek(); 
    } 
}