Dada uma sequência de dados (pode haver duplicatas), uma janela móvel de tamanho fixo, mova a janela a cada iteração desde o início da sequência de dados, de modo que (1) o elemento de dados mais antigo seja removido da janela e um novo elemento de dados é empurrado para dentro da janela (2) encontre a mediana dos dados dentro da janela a cada moviment

Os posts a seguir não são útei

Efetivamente, para encontrar o valor mediano de uma sequência aleatória

juntar dados com base em uma janela de tempo em movimento em R

Minha ideia

Use 2 pilhas para manter a mediana. Ao lado da janela, classifique os dados na janela na primeira iteração, o heap mínimo retém a parte maior e o heap máximo retém a parte menor. Se a janela tiver um número ímpar de dados, o heap máximo retornará a mediana, caso contrário, a média aritmética dos elementos principais dos dois heaps será a mediana.

Quando um novo dado for empurrado para a janela, remova os dados mais antigos de um dos heap e compare-os com a parte superior do heap max e min, para decidir qual heap os dados devem ser colocados. Em seguida, encontre a mediana como na primeira iteraçã

Mas, como encontrar um elemento de dados em um heap é um problema. Heap é uma árvore binária e não uma árvore de pesquisa binária.

possível resolvê-lo com O (n) ou O (n * lg m) em que m é o tamanho e o espaço da janela: O (1

ualquer ajuda é realmente apreciad

Obrigad