搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255字节。假设目前有一千万个查询记录（重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门）。现要统计最热门的1 0个查询串，且要求使用的内存不能超过1GB。以下各方法中，可行且效率最高的方法是（ ）。
- A.将一千万个查询串存入数组并进行快速排序，再统计其中每个查询串重复的次数
- B.将一千万个查询串存入数组并进行堆排序，再统计其中每个查询串重复的次数
- C.利用哈希表保存所有的查询串并记下每个查询串的重复次数，再利用小根堆选出重复次数最多的1 0个查询串
- D.利用哈希表保存所有的查询串并记下每个查询串的重复次数，再利用大根堆选出重复次数最多的1 0个查询串
正确答案及解析
正确答案
C
解析
此题也是考查对基本算法的理解运用，首先快速排序方法是不适合于这种情况的，由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte, 可以考虑把他们都放进内存中去,300万X255=765M，不会超过1G，因此可以用Hash_Map的思路。先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加1即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比，采用最小堆这种数据结构代替数组，把查找目标元素的时间复杂度降到了0(logk)，我们最终的时间复杂度是：O（N） + N*O（logK）。（N为1000万，N’为300万）。这是一道百度面试题。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案