2013.7.2-待字闺中-Google面试题：搜索之星 | 源代码

2013.7.2-待字闺中-Google面试题：搜索之星 | 源代码

题目描述：

给你一天的Google搜索日志，你怎么设计算法找出是否有一个搜索词，它出现的频率占所有搜索的一半以上？如果肯定有一个搜索词占大多数，你能怎么提高你的算法找到它？再假定搜索日志就是内存中的一个数组，能否有O(1)空间，O(n)时间的算法？

算法一：

定义一个哈希表，里面存放数组里面的每个元素以及出现的次数。可以通过两个过程来做。

第一步是映射，将每个元素放进去，存在加一，不存在置一。同时统计元素个数。

第二步是遍历整个哈希表，判断是否找到出现次数大于数组长度一半的。如果有，找到。否则没有。

显然，这个要求O(n)的空间在存储哈希表，并不理想。

算法二：

先将元素排序，然后再进行判断。因为如果有大多数的话，取数组中间点的那个元素即为所要找的那个。不过这种方法首先排序就需要O(NlogN)的时间复杂度，并不是很理想。

算法三：

假设我们一开始从数组的开头，碰到某个元素的时候，就设置该元素为当前元素。当前出现的次数为1，后面，如果接着碰到的元素和该元素相同，则当前次数加1，否则减1。如果当前出现的次数为0，则表示当前元素不确定。如果结合我们有大多数元素这个前提的话，必然最后的结果是大于0的，而且最终获取到的值就是大多数元素。

Read full article from 2013.7.2-待字闺中-Google面试题：搜索之星 | 源代码