Dodomeki
Sign in

111. Median in a Stream

Hard

Process a list of operations in order. {"tipo":"adicionar","valor":n} inserts an integer into the set; {"tipo":"mediana"} asks for the median of the values inserted so far. Return a list with one answer for each query. When there is an even number of values, use the average of the two middle values.

Example 1
Input: operacoes = [{tipo: adicionar, valor: 6}, {tipo: mediana}, {tipo: adicionar, valor: 2}, {tipo: mediana}]
Output: [6, 4]
Example 2
Input: operacoes = [{tipo: adicionar, valor: -3}, {tipo: adicionar, valor: 7}, {tipo: mediana}]
Output: [2]
Constraints
  • 1 <= operacoes.length <= 10^5
  • Toda consulta ocorre depois de pelo menos uma adição.
  • -10^9 <= valor <= 10^9
HeapDesign
Caso 1
operacoes =
[{"tipo":"adicionar","valor":6},{"tipo":"mediana"},{"tipo":"adicionar","valor":2},{"tipo":"mediana"}]
Expected =
[6,4]
Caso 2
operacoes =
[{"tipo":"adicionar","valor":-3},{"tipo":"adicionar","valor":7},{"tipo":"mediana"}]
Expected =
[2]

Run checks these 2 cases. Submit runs all 6, including hidden ones.