dynamically找最近m个数里最大的那个 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

dynamically找最近m个数里最大的那个

dynamically找最近m个数里最大的那个# JobHunting - 待字闺中

r*k2014-07-20 07:07

1 楼

咋做？
实际就是搜索引擎最近30分钟内频率最高的query吧？
我想到一个循环数组记堆内index
然后用堆存数值
每来一个新数，把新数放到要扔掉的老数的位置
然后update堆
不过index会变化比较多

l*a2014-07-20 07:07

2 楼

一个queue,keep the latest m , the head keep the oldest
another queue, keep the biggest among recent m
when u have a new number,remove all those less than it and then add it to
the tail of the queue.
when u remove a number from the first queue, once it is the head of 2nd
queue,remove both of them

【在 r*******k 的大作中提到】

: 咋做？
: 实际就是搜索引擎最近30分钟内频率最高的query吧？
: 我想到一个循环数组记堆内index
: 然后用堆存数值
: 每来一个新数，把新数放到要扔掉的老数的位置
: 然后update堆
: 不过index会变化比较多

y*n2014-07-20 07:07

3 楼

another queue, keep the biggest among recent m,
这个Queue 要多大。。

【在 l*****a 的大作中提到】

: 一个queue,keep the latest m , the head keep the oldest
: another queue, keep the biggest among recent m
: when u have a new number,remove all those less than it and then add it to
: the tail of the queue.
: when u remove a number from the first queue, once it is the head of 2nd
: queue,remove both of them

l*a2014-07-20 07:07

4 楼

at most m

【在 y***n 的大作中提到】

: another queue, keep the biggest among recent m,
: 这个Queue 要多大。。