s*******n 发帖数: 1018 | 1 如何计算纯文本中每个单词出现的次数,使用何种数据结构,复杂度多少,如果按照字
母顺序,复杂度
又是多少?
实在害怕算法题,一看就头大。
没点头绪。谢谢 |
s***r 发帖数: 12 | 2 hashmap,O(n)
如果按字母顺序,treemap,O(nlgn) |
p********7 发帖数: 549 | 3 不按照顺序用hash,如果按照顺序用trie,复杂度都是O(N) |
y*********e 发帖数: 518 | 4 按照顺序也可以用Balanced BST,比如RBTree。Java里面的TreeMap是一个RBTree。
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不按照顺序用hash,如果按照顺序用trie,复杂度都是O(N)
|
j****a 发帖数: 55 | 5 为啥hashmap也是O(n)啊?既然hash了,为啥不是O(1)? |
x****k 发帖数: 2932 | |
y*******o 发帖数: 6632 | 7 you still need to go through the file to construct the map.
after construction, it is 1.
【在 j****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为啥hashmap也是O(n)啊?既然hash了,为啥不是O(1)?
|
I**A 发帖数: 2345 | 8 trie怎么用?leaf上带个counter?
【在 x****k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 比较优化的还是用trie。
|
d*********i 发帖数: 628 | |
s*******n 发帖数: 1018 | 10 tree上都存什么?如果hashmap怎么存各单词和counter?
能给解释怎么考虑的吗?实在不知从何下手
多谢 |
n*******9 发帖数: 1017 | |
c******t 发帖数: 1500 | 12 tree的话为什么是O(n)呢?我怎么觉得是 O(nlogn) 呀?
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不按照顺序用hash,如果按照顺序用trie,复杂度都是O(N)
|