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 的大作中提到】
: TrieNode上加个call times field,然后用搜索结果放到SortedSet里就可以
: ，创建TrieNode时指定一个排序的方法，按照call times排即可。时间复杂度O(nlgn)
: ，n是Trie搜索的结果长度。
|
e********2
发帖数: 495 | 4 https://en.wikipedia.org/wiki/Treap
【在 e********3 的大作中提到】
:
: 不懂.
: 比如你输入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 的大作中提到】
: 这个treap如何应用到这道题上?
: 比如:
: 名字 call times
: abc 50
: abcd 100
: abd 200
: 怎么通过call times在trie中进行排序?
|
F********y
发帖数: 400 | 7 Inverted index就够了吧，不知道面试官是不是想问这个。
然而数据量不大的话，其实复杂度比trie高啊。 |
