z****3 发帖数: 782 | 1 Given a stream of search strings, write a function so that it returns the
top 10 in constant time.
应该怎么实现?我目前想到的是弄一个list来保存top 10,然后每次来新的就更新这个
list
求建议 |
U***A 发帖数: 849 | |
d**********6 发帖数: 4434 | 3 heap有问题,不pop的话只有top 1,pop的话pop出来的数据就丢失,而且pop不是O(1)的
应该要用hashmap+sorted list
【在 U***A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : heap
|
k*******q 发帖数: 5493 | 4 这是写LFU吗?
【在 z****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a stream of search strings, write a function so that it returns the : top 10 in constant time. : 应该怎么实现?我目前想到的是弄一个list来保存top 10,然后每次来新的就更新这个 : list : 求建议
|
d**********6 发帖数: 4434 | 5 这样吧,一个hashmap,key是search string, value是一个node
structur ListNode{
int val
ListNode pre
ListNode next
}
node组成一个double link list,每次遇到一个search string,在hashmap里面找对应
node,更新node的val,同时都跟pre node的数值比较发现有变化的就swap
取top10的时候就从double link list的头开始取就行
)的
【在 d**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : heap有问题,不pop的话只有top 1,pop的话pop出来的数据就丢失,而且pop不是O(1)的 : 应该要用hashmap+sorted list
|
C****t 发帖数: 53 | 6 class Node:
def __init__(key, val)
self.key = key
self.val = val
maps[node.key] = node
class LinkedList:
# if node.key comes in again, then increase node.val by 1, delete the old
node
def remove(self, node)
# insert the updated node
def add(self,node)
# return Top K:
def topK():
【在 z****3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Given a stream of search strings, write a function so that it returns the : top 10 in constant time. : 应该怎么实现?我目前想到的是弄一个list来保存top 10,然后每次来新的就更新这个 : list : 求建议
|
n*****g 发帖数: 178 | 7
)的
top K 问题好像还是用heap比较好吧
【在 d**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : heap有问题,不pop的话只有top 1,pop的话pop出来的数据就丢失,而且pop不是O(1)的 : 应该要用hashmap+sorted list
|
d**********6 发帖数: 4434 | 8 你要看要求啊,你用heap
不pop的话只有top1
pop出来以后这个数值就丢失了。你后面还要继续计数的话咋办?而且pop又不是O(1)
【在 n*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : )的 : top K 问题好像还是用heap比较好吧
|
s*******u 发帖数: 89 | 9 size为10的min-heap吖,每次把最小pop的出去,最后剩在堆里的就是最大的10个 |
d**********6 发帖数: 4434 | 10 这样这个堆永远只有前10个了。第11个count是1,然后被踢出去。第11个又来,因为前
面被踢出去了,重置,count还是1,又被踢出去了。。。
【在 s*******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : size为10的min-heap吖,每次把最小pop的出去,最后剩在堆里的就是最大的10个
|
s*******u 发帖数: 89 | 11 喵~我的意思是,hash先得到counts,counts再丢进heap....
【在 d**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样这个堆永远只有前10个了。第11个count是1,然后被踢出去。第11个又来,因为前 : 面被踢出去了,重置,count还是1,又被踢出去了。。。
|
d**********6 发帖数: 4434 | 12 用heap始终有这个问题,pop完之后就丢失了
比如我读了100个key以后,读一次top 10,这时候heap就空了。你就没法重新追踪下去
,后面的再进来的会乱套
至少也要是一个sorted array,读取top 10的时候不需要pop出来
【在 s*******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 喵~我的意思是,hash先得到counts,counts再丢进heap....
|
a*****2 发帖数: 96 | 13 这不是挺好的solution吗,怎么没人顶呢
【在 d**********6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这样吧,一个hashmap,key是search string, value是一个node : structur ListNode{ : int val : ListNode pre : ListNode next : } : node组成一个double link list,每次遇到一个search string,在hashmap里面找对应 : node,更新node的val,同时都跟pre node的数值比较发现有变化的就swap : 取top10的时候就从double link list的头开始取就行 :
|