e********3 发帖数: 229 | 1 题目就是类似电话里通讯录的搜索功能. 输入一个人人名的前几个字母,会弹出一堆有
相同前几个字母的人.但是这些人要根据被拨打次数的多少从高到低进行排序.面试官貌
似不是想要trie的做法,而且用trie的话因为要排序那这个搜索时间也应该很长. 求大
牛解答 |
l******s 发帖数: 3045 | 2 TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以
,创建TrieNode时指定一个排序的方法,按照call times排即可。时间复杂度O(nlgn)
,n是Trie搜索的结果长度。 |
e********3 发帖数: 229 | 3
不懂.
比如你输入a, 那你要搜索a下面所有trienode,然后再把搜索结果进行排序吧?
"创建TrieNode时指定一个排序的方法,按照call times排即可"
这是什么意思
【在 l******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以 : ,创建TrieNode时指定一个排序的方法,按照call times排即可。时间复杂度O(nlgn) : ,n是Trie搜索的结果长度。
|
e********2 发帖数: 495 | 4 https://en.wikipedia.org/wiki/Treap
【在 e********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不懂. : 比如你输入a, 那你要搜索a下面所有trienode,然后再把搜索结果进行排序吧? : "创建TrieNode时指定一个排序的方法,按照call times排即可" : 这是什么意思
|
e********3 发帖数: 229 | 5 这个treap如何应用到这道题上?
比如:
名字 call times
abc 50
abcd 100
abd 200
怎么通过call times在trie中进行排序? |
l******s 发帖数: 3045 | 6 有笔误,应该是创建SortedSet时指定一个排序方法。比如下面:
SortedSet ss = new SortedSet(Comparer.Create((
a, b) => a.CallTimes == b.CallTimes ? a.PhoneName.CompareTo(b.PhoneName) : b.
CallTimes.CompareTo(a.CallTimes)));
我用的是C#,Java也有类似的创建自定义的排序的Compare的方法。
【在 e********3 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个treap如何应用到这道题上? : 比如: : 名字 call times : abc 50 : abcd 100 : abd 200 : 怎么通过call times在trie中进行排序?
|
F********y 发帖数: 400 | 7 Inverted index就够了吧,不知道面试官是不是想问这个。
然而数据量不大的话,其实复杂度比trie高啊。 |