[朋友面的G]Find k largest element in sliding window - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

[朋友面的G]Find k largest element in sliding window

[朋友面的G]Find k largest element in sliding window# JobHunting - 待字闺中

z*e2015-03-25 07:03

1 楼

http://articles.leetcode.com/2011/01/sliding-window-maximum.htm
这个题目变种，如果不是找最大值，而是找这个window的top K elements，（打出所
有的top k），window size is N, assume k < N, array is a integer stream. 可以
有O(N)解法吗? 朋友式常规的NlgK, 用min heap.
多谢。

z*e2015-03-25 07:03

2 楼

顶一下

z*m2015-03-25 07:03

3 楼

用min heap不行吧，当出了左边window boundary，就必须从heap里删掉，即使是全局
最大的

z*e2015-03-25 07:03

4 楼

你说的是对的。应该是当时听得时候马马虎虎，min heap O(NlgK)是不行的。
比如
{1， 3， -1，0, 5, -2, 6, 7} K = 2, window size (W) = 4, N is the size of
the stream
{1， 3， [-1，0, 5, -2], 6, 7}
基本上每一次都要重新扫一遍window，O(N* WlgK) 的解法。。
感觉这样弱爆了啊

【在 z***m 的大作中提到】

: 用min heap不行吧，当出了左边window boundary，就必须从heap里删掉，即使是全局
: 最大的

P*r2015-03-25 07:03

5 楼

是不是该用BST. 进window就add，出window就remove

y*h2015-03-25 07:03

6 楼

Data mining里有lossy的算法，你去搜top k data stream 三大类方法

z*m2015-03-25 07:03

7 楼

是top k 还是top K frequent啊？

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

: Data mining里有lossy的算法，你去搜top k data stream 三大类方法

s*h2015-03-25 07:03

8 楼

和mean差不多吧，用两个tree? 一个存前k，另一个存w-k,然后就可以进进出出了，这
样可以N*lng(K)吧。

g*v2015-03-25 07:03

9 楼

circular array 来keep这个window。
BST来找top k。
如果更快的话可以hashmap下array的element 到 BST
heap不行的原因是删除的时候麻烦。

a*22015-03-25 07:03

10 楼

circular buffer + hashmap + sorted double linkedlist

z*e2015-03-25 07:03

11 楼

是top k,not top k frequent

【在 z***m 的大作中提到】

: 是top k 还是top K frequent啊？

z*e2015-03-25 07:03

12 楼

不行的，你要把top k大的树打出来，遍历第一个树也是k，所以你的是N*K*LgK

【在 s*******h 的大作中提到】

: 和mean差不多吧，用两个tree? 一个存前k，另一个存w-k,然后就可以进进出出了，这
: 样可以N*lng(K)吧。

z*e2015-03-25 07:03

13 楼

assume 你的bst是W，打出top需要K，所以你的复杂度还是N*K*lgW

【在 g****v 的大作中提到】

: circular array 来keep这个window。
: BST来找top k。
: 如果更快的话可以hashmap下array的element 到 BST
: heap不行的原因是删除的时候麻烦。

z*e2015-03-25 07:03

14 楼

Lossy感觉就是一个counting sort的算法？这里怎么能有效解决top k大的数呢？不是
top k 频繁的数

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

: Data mining里有lossy的算法，你去搜top k data stream 三大类方法

z*e2015-03-25 07:03

15 楼

你的也是N*K*lgW吧

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

: circular buffer + hashmap + sorted double linkedlist

P*r2015-03-25 07:03

16 楼

你考虑对sliding window有特别的考虑了吗？
如果样本一共X个，那用min heap就是 X*N*logK.
用BST的话，就是X*(logN + K). logN是用来插到树里,K是用来打印

：你的也是N*K*lgW吧
：【在 asd2002 (大王) 的大作中提到: 】

i*t2015-03-25 07:03

17 楼

sliding window 扫一边的话，top K 与整个数组的top K不是一模一样么。看不
出sliding window 在这种情况下有啥区别。

【在 z**********e 的大作中提到】

: http://articles.leetcode.com/2011/01/sliding-window-maximum.htm
: 这个题目变种，如果不是找最大值，而是找这个window的top K elements，（打出所
: 有的top k），window size is N, assume k < N, array is a integer stream. 可以
: 有O(N)解法吗? 朋友式常规的NlgK, 用min heap.
: 多谢。

i*e2015-03-25 07:03

18 楼

这个问题有两个操作，一个是push a new element from stream into the data
strucutre, 另一个是print the current top K elements。你的O(N)要求是哪个操作
？如果是第二个话前面的circular buffer + hashmap + sorted double linkedlist完
全可以的吧，只要O(K)，只不过就是在第一个操作时候insert new element时候代价较
大, O(N), 如果dbllinkedlist换成heap的话insert时候能省不少时间，print时候就变
成 log(N*(N-1)...*(N-K)) => O(Klog(N)). 不知道这样想对不对？

f*52015-03-25 07:03

19 楼

BST, O (n*(logW+k))
void printBST(multiset > &BST, int k){
int i=0;
multiset >::iterator it=BST.begin();
for(;icout<++it;
}
cout<}
void topK_SlideWindow(vector &A, int w, int k){
//use BST tree to record w elems in the windows.
//update BST, add new elem into BST, and delete old elem.
assert(A.size()>=w&&k<=w);
multiset >BST;
for(int i=0;iBST.insert(A[i]);
}
printBST(BST, k);
for(int i=w;iauto it=BST.find(A[i-w]);
BST.erase(it);
BST.insert(A[i]);
printBST(BST,k);
}

}

t*e2015-03-25 07:03

20 楼

这个方法具体怎么实现？

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

: circular buffer + hashmap + sorted double linkedlist

x*n2015-03-25 07:03

21 楼

BST删除和添加元素也要调整，不如heap来得快。

【在 g****v 的大作中提到】

: circular array 来keep这个window。
: BST来找top k。
: 如果更快的话可以hashmap下array的element 到 BST
: heap不行的原因是删除的时候麻烦。

c*82015-03-25 07:03

22 楼

如果是Java的话，TreeSet （BST）不允许duplicates，那怎么办呢？

【在 f******5 的大作中提到】

: BST, O (n*(logW+k))
: void printBST(multiset > &BST, int k){
: int i=0;
: multiset >::iterator it=BST.begin();
: for(;i: cout<: ++it;
: }
: cout<: }

c*n2015-03-25 07:03

23 楼

怎么讨论这么长还是不着边？
lint code. 上有基本是原题
sliding window median. max heap plus mean heap

【在 z**********e 的大作中提到】