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 的大作中提到】
: heap
|
k*******q
发帖数: 5493 | 4 这是写LFU吗？
【在 z****3 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
:
: )的
: 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 的大作中提到】
: size为10的min-heap吖，每次把最小pop的出去，最后剩在堆里的就是最大的10个
|
s*******u
发帖数: 89 | 11 喵～我的意思是，hash先得到counts，counts再丢进heap....
【在 d**********6 的大作中提到】
: 这样这个堆永远只有前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 的大作中提到】
: 喵～我的意思是，hash先得到counts，counts再丢进heap....
|
a*****2
发帖数: 96 | 13 这不是挺好的solution吗，怎么没人顶呢
【在 d**********6 的大作中提到】
: 这样吧，一个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的头开始取就行
:
|
