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 的大作中提到】
: 不按照顺序用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 的大作中提到】
: 为啥hashmap也是O(n)啊？既然hash了，为啥不是O(1)?
|
I**A
发帖数: 2345 | 8 trie怎么用?leaf上带个counter?
【在 x****k 的大作中提到】
: 比较优化的还是用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 的大作中提到】
: 不按照顺序用hash，如果按照顺序用trie，复杂度都是O（N）
|
