z**********e
发帖数: 12 | 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**********e
发帖数: 12 | |
z***m
发帖数: 1602 | 3 用min heap不行吧，当出了左边window boundary，就必须从heap里删掉，即使是全局
最大的 |
z**********e
发帖数: 12 | 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******r
发帖数: 1342 | 5 是不是该用BST. 进window就add，出window就remove |
y*****h
发帖数: 97 | 6 Data mining里有lossy的算法，你去搜top k data stream 三大类方法 |
z***m
发帖数: 1602 | 7 是top k 还是top K frequent啊？
【在 y*****h 的大作中提到】
: Data mining里有lossy的算法，你去搜top k data stream 三大类方法
|
s*******h
发帖数: 105 | 8 和mean差不多吧，用两个tree? 一个存前k，另一个存w-k,然后就可以进进出出了，这
样可以N*lng(K)吧。 |
g****v
发帖数: 971 | 9 circular array 来keep这个window。
BST来找top k。
如果更快的话可以hashmap下array的element 到 BST
heap不行的原因是删除的时候麻烦。 |
a*****2
发帖数: 96 | 10 circular buffer + hashmap + sorted double linkedlist |
|
|
z**********e
发帖数: 12 | 11 是top k,not top k frequent
【在 z***m 的大作中提到】
: 是top k 还是top K frequent啊？
|
z**********e
发帖数: 12 | 12 不行的，你要把top k大的树打出来，遍历第一个树也是k，所以你的是N*K*LgK
【在 s*******h 的大作中提到】
: 和mean差不多吧，用两个tree? 一个存前k，另一个存w-k,然后就可以进进出出了，这
: 样可以N*lng(K)吧。
|
z**********e
发帖数: 12 | 13 assume 你的bst是W，打出top需要K，所以你的复杂度还是N*K*lgW
【在 g****v 的大作中提到】
: circular array 来keep这个window。
: BST来找top k。
: 如果更快的话可以hashmap下array的element 到 BST
: heap不行的原因是删除的时候麻烦。
|
z**********e
发帖数: 12 | 14 Lossy感觉就是一个counting sort的算法？这里怎么能有效解决top k大的数呢？不是
top k 频繁的数
【在 y*****h 的大作中提到】
: Data mining里有lossy的算法，你去搜top k data stream 三大类方法
|
z**********e
发帖数: 12 | 15 你的也是N*K*lgW吧
【在 a*****2 的大作中提到】
: circular buffer + hashmap + sorted double linkedlist
|
P******r
发帖数: 1342 | 16 你考虑对sliding window有特别的考虑了吗？
如果样本一共X个，那用min heap就是 X*N*logK.
用BST的话，就是X*(logN + K). logN是用来插到树里,K是用来打印
：你的也是N*K*lgW吧
：【 在 asd2002 (大王) 的大作中提到: 】 |
i*********t
发帖数: 16 | 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*******e
发帖数: 7 | 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******5
发帖数: 104 | 19 BST, O (n*(logW+k))
void printBST(multiset > &BST, int k){
int i=0;
multiset >::iterator it=BST.begin();
for(;i
cout<<(*it)<<",";
++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;i
BST.insert(A[i]);
}
printBST(BST, k);
for(int i=w;i
auto it=BST.find(A[i-w]);
BST.erase(it);
BST.insert(A[i]);
printBST(BST,k);
}
} |
t*******e
发帖数: 274 | 20
这个方法具体怎么实现？
【在 a*****2 的大作中提到】
: circular buffer + hashmap + sorted double linkedlist
|
|
|
x*****n
发帖数: 195 | 21 BST删除和添加元素也要调整，不如heap来得快。
【在 g****v 的大作中提到】
: circular array 来keep这个window。
: BST来找top k。
: 如果更快的话可以hashmap下array的element 到 BST
: heap不行的原因是删除的时候麻烦。
|
c****8
发帖数: 76 | 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)<<",";
: ++it;
: }
: cout<: }
|
c******n
发帖数: 4965 | 23 怎么讨论这么长还是不着边？
lint code. 上有基本是原题
sliding window median. max heap plus mean heap
【在 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.
: 多谢。
|
