f*********d
发帖数: 140 | 1 走过路过的大牛请指教：
Given a sequence of data (it may have duplicates), a fixed-sized moving
window, move the window at each iteration from the start of the data
sequence, such that the oldest data element is removed from the window and a
new data element is pushed into the window，how to find the median of the
data inside the window at each moving? |
g*********e
发帖数: 14401 | 2 用一个max-min-heap来存储window里面的数
复杂度Nlogk |
t*********h
发帖数: 941 | 3 一个简单的方法就是维护一个Priority queue吧 随时更新
a
【在 f*********d 的大作中提到】
: 走过路过的大牛请指教：
: Given a sequence of data (it may have duplicates), a fixed-sized moving
: window, move the window at each iteration from the start of the data
: sequence, such that the oldest data element is removed from the window and a
: new data element is pushed into the window，how to find the median of the
: data inside the window at each moving?
|
f*********d
发帖数: 140 | |
s***5
发帖数: 2136 | 5 a linked list + a min heap + a max heap |
f*********d
发帖数: 140 | 6 收到～ 多谢大牛！
【在 s***5 的大作中提到】
: a linked list + a min heap + a max heap
|
l*n
发帖数: 529 | 7 linked list 这里干嘛用的？用来标记谁该删除？要是在heap中间挖个洞还是挺麻烦的
吧。
【在 s***5 的大作中提到】
: a linked list + a min heap + a max heap
|
a******e
发帖数: 710 | 8 求详细解释
【在 s***5 的大作中提到】
: a linked list + a min heap + a max heap
|
c********e
发帖数: 186 | 9 你觉得这样行不行：
1）删除： Map记录一个元素在heap有的位置，然后相应删除
2）不删除：假设原数组A
一个min heap，一个max heap，一个数组B，B_i表示A_i放在哪个heap里面，0初始值，
1放min heap， 2放max heap。 另外记录min heap和max heap的size，这个size不是
min heap里面的元素的个数，而是里面有效元素即在window里面元素的个数。然后维持
两个heap里面有效元素个数<=1.当一个元素移出window的时候查看在哪个heap，哪个
heap的size就减一。当然挪动一个元素到另外一个heap要更新B和有效size。当extract
min 或者max，如果已无效，则直接remove， 再取下一个。 |
k***7
发帖数: 6 | 10 窗口大小为N
list大小为N，顺序存放数值以及记录元素在heap中的存放的Element address[这个不
随堆的调整而变化]
min heap大小为 N/2
max heap大小为 N-N/2
median为max heap顶上元素，access time O(1)
维护堆：list[0]要被下一个新数n替代
if(list[0]<=median){//list[0] is in max heap
remove(list[0], maxHeap);
if(n>maxHeap.top()) {
insert(n, minHeap);
insert(minHeap.top(), maxHeap);
minHeap.pop();
} else {
insert(n, maxHeap);
}
} else { //list[o] is in min heap
remove(list[0], minHeap);
if(n>maxHeap.top()) {
insert(n, minHeap);
} else {
insert(n, maxHeap);
insert(maxHeap.top(), minHeap);
minHeap.pop();
}
} |
