m***n
发帖数: 2154 | 1 find out K most frequent numbers from incoming streams of numbers on the fly
我的方法是 保存 一个hashtable
value---->(int frequency, boolean inHeap)
每一个值，都保存一个频率和是否在heap上
一个MIN Heap, Heap上保存value,frequency, 但只比较frequency
大家还有更好办法么？ |
l*********8
发帖数: 4642 | 2 frequency是从steam开始的时候累计计数吗？ 还是有一个time window？
fly
【在 m***n 的大作中提到】
: find out K most frequent numbers from incoming streams of numbers on the fly
: 我的方法是 保存 一个hashtable
: value---->(int frequency, boolean inHeap)
: 每一个值，都保存一个频率和是否在heap上
: 一个MIN Heap, Heap上保存value,frequency, 但只比较frequency
: 大家还有更好办法么？
|
m***n
发帖数: 2154 | 3 开始时计数啊。
【在 l*********8 的大作中提到】
: frequency是从steam开始的时候累计计数吗？ 还是有一个time window？
:
: fly
|
p*****2
发帖数: 21240 | 4 Hashtable stores frequency.
For each coming number, add it and frequency into max heap. |
l*********8
发帖数: 4642 | 5 我觉得像马兰说的， hashtable还需要保存IsInHeap的flag。 不然heap里面怎么避免
duplicated item?
【在 p*****2 的大作中提到】
: Hashtable stores frequency.
: For each coming number, add it and frequency into max heap.
|
m***n
发帖数: 2154 | 6 显然是min heap, 只保存K 最大的。
来一个新的数， 只有4种可能：
1. 不在min heap里面，而且frequency 小于 top of the min heap
2. 不在min heap里面，frequncy 大于top of the min heap
3. 在min heap里面，但不是最小的
4. 在min heap里面，是最小的
【在 p*****2 的大作中提到】
: Hashtable stores frequency.
: For each coming number, add it and frequency into max heap.
|
h**********l
发帖数: 6342 | 7 你存这个inheap显然不好，你还要往heap里面加过来后才能回来update这个flag
之用保存一个 min，然后直接看是不是在heap里面就好了
fly
【在 m***n 的大作中提到】
: find out K most frequent numbers from incoming streams of numbers on the fly
: 我的方法是 保存 一个hashtable
: value---->(int frequency, boolean inHeap)
: 每一个值，都保存一个频率和是否在heap上
: 一个MIN Heap, Heap上保存value,frequency, 但只比较frequency
: 大家还有更好办法么？
|
l*********8
发帖数: 4642 | 8 是minheap, 因为要插入新的frequent item into the heap的时候， 要删除的是原来
heap里面最不frequent的item.
【在 m***n 的大作中提到】
: 显然是min heap, 只保存K 最大的。
: 来一个新的数， 只有4种可能：
: 1. 不在min heap里面，而且frequency 小于 top of the min heap
: 2. 不在min heap里面，frequncy 大于top of the min heap
: 3. 在min heap里面，但不是最小的
: 4. 在min heap里面，是最小的
|
p*****2
发帖数: 21240 | 9 有duplicate无所谓。只加不删除。删除的话performance可就受影响了。 |
p*****2
发帖数: 21240 | 10 if(!ht.containsKey(n))
ht.put(n,0);
ht.put(n, ht.get(n)+1);
maxheap.add(new Freq(n, ht.get(n)); 就可以了。 |
|
|
h**********l
发帖数: 6342 | 11 worse case你的heap太大了把，所有的东西都要加进去
当然这个具体可以优化
【在 p*****2 的大作中提到】
: 有duplicate无所谓。只加不删除。删除的话performance可就受影响了。
|
p*****2
发帖数: 21240 | 12
这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。
【在 h**********l 的大作中提到】
: worse case你的heap太大了把，所有的东西都要加进去
: 当然这个具体可以优化
|
m***n
发帖数: 2154 | 13 如果要删除的话，要用BST .
【在 p*****2 的大作中提到】
:
: 这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。
|
h**********l
发帖数: 6342 | 14 ？？？
heap删除跟bst有什么关系？
【在 m***n 的大作中提到】
: 如果要删除的话，要用BST .
|
m***n
发帖数: 2154 | 15 我说的是如果数字不仅仅增加，还可能减小的情况。
【在 h**********l 的大作中提到】
: ？？？
: heap删除跟bst有什么关系？
|
m***n
发帖数: 2154 | 16 这个你只增加，不是意味着一个num保存了无数个freq对象？
任意来一个数字，你都增加一个freq对象，内存受得了？
【在 p*****2 的大作中提到】
: if(!ht.containsKey(n))
: ht.put(n,0);
: ht.put(n, ht.get(n)+1);
: maxheap.add(new Freq(n, ht.get(n)); 就可以了。
|
l*********8
发帖数: 4642 | 17 你是怎么从堆中删除元素的？ 或许可以改进删除方法
【在 p*****2 的大作中提到】
:
: 这情况我碰到几次了。都这么做的。删除的perf不行，过不了test case。
|
l*********8
发帖数: 4642 | 18 在这个例子里面，如果使用min heap,应该是把新加入item替换原来的堆顶item,然后调
整新item的位置，是log(k)代价。
【在 l*********8 的大作中提到】
: 你是怎么从堆中删除元素的？ 或许可以改进删除方法
|
h**********l
发帖数: 6342 | 19 感觉按照题目，不会频率减小，但是多想也挺好
【在 m***n 的大作中提到】
: 我说的是如果数字不仅仅增加，还可能减小的情况。
|
l*********8
发帖数: 4642 | 20 如果frequency只是计算time window里的，比如说过去24小时. 那么频率就会减小。
【在 h**********l 的大作中提到】
: 感觉按照题目，不会频率减小，但是多想也挺好
|
|
|
h**********l
发帖数: 6342 | 21 对，这样会减小
【在 l*********8 的大作中提到】
: 如果frequency只是计算time window里的，比如说过去24小时. 那么频率就会减小。
|
p*****2
发帖数: 21240 | 22
达到一定程度一次性丢掉就可以了。
if(maxheap.size()>N)
{
new maxheap
copy K elements into new maxheap
delete old max heap
}
【在 m***n 的大作中提到】
: 这个你只增加，不是意味着一个num保存了无数个freq对象？
: 任意来一个数字，你都增加一个freq对象，内存受得了？
|
l*********8
发帖数: 4642 | 23 But the first K elements can also have duplications.
【在 p*****2 的大作中提到】
:
: 达到一定程度一次性丢掉就可以了。
: if(maxheap.size()>N)
: {
: new maxheap
: copy K elements into new maxheap
: delete old max heap
: }
|
z********c
发帖数: 72 | 24 每次都要添加元素到maxheap里么？那MaxHeap的大小超过了K怎么办？
【在 p*****2 的大作中提到】
: if(!ht.containsKey(n))
: ht.put(n,0);
: ht.put(n, ht.get(n)+1);
: maxheap.add(new Freq(n, ht.get(n)); 就可以了。
|
w****x
发帖数: 2483 | 25 我觉得就是hashtable + minheap
之前的数的频率肯定是要的存储的, 哪怕只是第一个数只出现了一次
维护k大的数我觉得可以就用一个排序数组, 因为每次一个数只加1,所以只需要和最小
的比较(不在数组内的情况)或第i-1个比较, 比如
5,4,3,3,2,1, 如果第4个数加1, ==> 5,4,3,4,2,1
只需要swap第3个数=> 5,4,4,3,2,1 貌似是O(1) ,如果重复情况太多可以修改成
更复杂的数据结构, 因该有办法说在发生改变的情况下达到O(1)
不过说实话, 实际跑起来肯定比用堆慢, hashtable + minheap因该最好 |
z********c
发帖数: 72 | 26 我很困惑的是，如果更新了一个元素的freq，然后这个元素属于minHeap，那么怎么更
新这个元素在heap中的位置？
【在 w****x 的大作中提到】
: 我觉得就是hashtable + minheap
: 之前的数的频率肯定是要的存储的, 哪怕只是第一个数只出现了一次
: 维护k大的数我觉得可以就用一个排序数组, 因为每次一个数只加1,所以只需要和最小
: 的比较(不在数组内的情况)或第i-1个比较, 比如
: 5,4,3,3,2,1, 如果第4个数加1, ==> 5,4,3,4,2,1
: 只需要swap第3个数=> 5,4,4,3,2,1 貌似是O(1) ,如果重复情况太多可以修改成
: 更复杂的数据结构, 因该有办法说在发生改变的情况下达到O(1)
: 不过说实话, 实际跑起来肯定比用堆慢, hashtable + minheap因该最好
|
p*****2
发帖数: 21240 | 27
这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。
【在 l*********8 的大作中提到】
: But the first K elements can also have duplications.
|
p*****2
发帖数: 21240 | 28
这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。
【在 l*********8 的大作中提到】
: But the first K elements can also have duplications.
|
w****x
发帖数: 2483 | 29
up shift, 局部向上调整
【在 z********c 的大作中提到】
: 我很困惑的是，如果更新了一个元素的freq，然后这个元素属于minHeap，那么怎么更
: 新这个元素在heap中的位置？
|
z********c
发帖数: 72 | 30 自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
到么?
【在 w****x 的大作中提到】
:
: up shift, 局部向上调整
|
|
|
w****x
发帖数: 2483 | 31
这种题不会叫写代码的
【在 z********c 的大作中提到】
: 自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
: 到么?
|
l*********8
发帖数: 4642 | 32 yes, this works.
【在 p*****2 的大作中提到】
:
: 这个倒是。不过一般做题的时候还要maitain 一个visited array来check这个。
|
l*********8
发帖数: 4642 | 33 c++ stl's priority_queue doesn't support updating privority. But boost
【在 z********c 的大作中提到】
: 自己实现一个heap是可以做到的，但是如果他要你写code，用标准库提供的容器可以做
: 到么?
|
z********c
发帖数: 72 | 34 heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
实现采用set
map freq;
set > bst;
bst的元素是一个的pair，以frequency排序
来一个str
1. f = freq[str] ++;
2. if (bst.find ((f, str)) != bst.end ()) {
// bst里有str了，那么更新str的freq值
bst.erase ((f, str))
bst.insert ((f + 1, str))
}
3. else
if (bst.size () < K)
// bst里元素不足K
bst.insert ((f + 1, str))
4. else
if (f + 1 > bst.begin ()->first) {
// str的freq大于bst中最小元素的freq
bst.erase (bst.begin ())
bst.insert ((f + 1, str))
}
【在 w****x 的大作中提到】
:
: 这种题不会叫写代码的
|
p*****2
发帖数: 21240 | 35 这个刚才我也想过
不过java里更新的时候要delete insert
heap不能解决频度发生改变时的调整，所以我想到的可以用hash BST解决，C 里BST的
实现采用setmap freq;set
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 z********c 的大作中提到】
: heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
: 实现采用set
: map freq;
: set > bst;
: bst的元素是一个的pair，以frequency排序
: 来一个str
: 1. f = freq[str] ++;
: 2. if (bst.find ((f, str)) != bst.end ()) {
: // bst里有str了，那么更新str的freq值
: bst.erase ((f, str))
|
l*********8
发帖数: 4642 | 36 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
【在 z********c 的大作中提到】
: heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
: 实现采用set
: map freq;
: set > bst;
: bst的元素是一个的pair，以frequency排序
: 来一个str
: 1. f = freq[str] ++;
: 2. if (bst.find ((f, str)) != bst.end ()) {
: // bst里有str了，那么更新str的freq值
: bst.erase ((f, str))
|
p*****2
发帖数: 21240 | 37 用hashtable找
既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 l*********8 的大作中提到】
: 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
|
z********c
发帖数: 72 | 38 why？logK呀？
【在 l*********8 的大作中提到】
: 既然你的bst是以frequency排序，那么 bst.find ((f, str)) 岂不是很慢。
|
l*********8
发帖数: 4642 | 39 你的key是frequency, 要查找string， 没办法用二分查找的啊。
【在 z********c 的大作中提到】
: why？logK呀？
|
z********c
发帖数: 72 | 40 key是的pair
【在 l*********8 的大作中提到】
: 你的key是frequency, 要查找string， 没办法用二分查找的啊。
|
|
|
l*********8
发帖数: 4642 | 41 你compare key的函数是什么？
【在 z********c 的大作中提到】
: key是的pair
|
l*********8
发帖数: 4642 | 42 default comparision between two pairs:
In inequality comparisons (<, >), the first elements are compared first, and
only if the inequality comparison is not true for them, the second elements
are compared.
【在 l*********8 的大作中提到】
: 你compare key的函数是什么？
|
P*A
发帖数: 189 | 43 用BST挺好，比heap维护更方便，
修改了一下，可以不用把pair当作key来排序，在hash里面记录BST结点的指针
multimap bst;
hash_map > hm;
foreach given key k
0. if(hm.find(k)==hm.end()) {
hm.insert(make_pair(k, make_pair(1, bst.end())));
if (bst.size () < K) {
// bst里元素不足K
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
continue;
}
1. f = ++hm[k].first;
2. if (hm[k].second != bst.end()) {
// bst里有k了，那么更新freq值
bst.erase (hm[k].second)
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
3. else
if (f > bst.begin()->first) {
// k的freq大于bst中最小元素的freq
bst.erase (bst.begin ())
t = bst.insert (make_pair(f, k))
hm[k].second = t;
}
【在 z********c 的大作中提到】
: heap不能解决频度发生改变时的调整，所以我想到的可以用hash+BST解决，C++里BST的
: 实现采用set
: map freq;
: set > bst;
: bst的元素是一个的pair，以frequency排序
: 来一个str
: 1. f = freq[str] ++;
: 2. if (bst.find ((f, str)) != bst.end ()) {
: // bst里有str了，那么更新str的freq值
: bst.erase ((f, str))
|
