百度的一个算法面试题

Question

我是学财管的，算法不是很好，当时百度一面的时候第一个就是算法题，最近在复习数据结构的时候突然想起来了，就拿出来跟大家讨论一下：从一堆关键字中找出访问量最多的TOP10当时没有答出来，现在想一下大概有这么三种思路：
1.冒泡排序，排10次选出10个最大的
2.堆排序，排10次选出10个最大的
上面两种的时间复杂度（应该是相同的）我不知道怎么算，但是为了从千万条数据中找出10个，而把所有的数据几乎循环10遍，这绝对不是什么好办法，于是我还有一个自己乱想的方法：
3.从假如有10万个关键字，用一个数组把前1-10条放进去，然后进行排序（排序这10条的时间可以忽略不计，因为10万太大了），然后拿出第11个往这个排好序的数组中插，如果值的范围在这个数组中，则把最一个（最小的）那个数挤出去，否则直接略过，然后12,13,14......n，直到n结束，然后那个数组中的就应该是已经排好序的top10，这里只遍历了1遍，然后我们需要考虑的就是插入这个过程了，由于数组中已经排好序了，所以插入的时候用二分法去找插入的位置，最多比较3次，所以总的时间要3*n，这样就比方法1,2好多了，是不？这是我的见解，大家有什么好办法可以分享啊

Answer 1

个人觉得这个算法不仅仅是排序，还有统计次数的问题关键是怎么让统计次数和排序结合起来效率最好  下面是一些个人想法，不一定正确在一堆关键字中找出访问最多的
那访问次数肯定有没有告诉你
那首先要做的应该是分析各个关键次的出现次数
假设这是一个数组string[xxxxxx];
可以直接用Arrays.sort(string);
对这个数组排序（目的是让同样的关键字排在连续的位置）
然后再对这个数组进行一次检索，用一个result对象记录
result对象有连个元素：<关键字，连续次数>，连续次数就是出现次数，
并把些这个result对象放到一个List中（最大为10）
当List满10之后有连续次数比当前List中最小值要大的result出现的时候，
替换进List，移除原最小值

Answer 2

访问次数在随着访问的时候，就已经统计出来了，而且Arrays.sort()...个人觉得不适合大量数据的排序的，这个绝对不适合的

Answer 3

Map<关键字,访问次数> 然后排序呢。欢迎拍砖

Answer 4

map 和最小堆结合 不就可以了么?

Answer 5

因为个人觉得经过Map<关键字,访问次数> 后,数组的长度会减少很多
 再用最小堆 二分查找插入 应该效果会快很多