本题目出自
@陈利人问题：
#Google面试题#给你一天的Google搜索日志，你怎么设计算法找出是否有一个搜索词，它出现的频率占所有搜索的一半以上？如果肯定有一个搜索词占大多数，你能怎么提高你的算法找到它？再假定搜索日志就是内存中的一个数组，能否有O(1)空间，O(n)时间的算法？
刚看到这个题目的时间吓坏了，好难啊，无从下手啊，为自己的之上捉急啊。。下班的班车上开始想这个问题，开始分析，其实这个搜索日志就是一个搜索词的集合嘛，甭管它有多大，总可以分成若干堆吧。既然这个搜索词超过一半，那么在这若干堆中分别找出来最流行的词中，也应该占一半吧。（这个应该没有理解错吧。）
这个时候我想可以把问题转换成一个整数数组，其中有个整数出现的次数超过一半，找出这个整数就OK了吧。要找出这个数组中出现次数超一半的值，本身这个算法应该很简单，但是O(1)空间和O(n)的时间复杂度，还是有点伤脑筋的。。:(，内存又不贵，为啥O(1)啊。。
因为那个数字出现的次数超过一半，我们可以想象一下，把那个数字标成1，其它的都是-1，把所有的数字加起来肯定大于0，对吧？因为超过一半嘛。。这个时候灵光乍现，用一个标杆来标志潜在的那个搜索词，一个整数count表示它出现的次数（准确的说不是它的次数，后面会解释），遍历整个数组
1) 如果当前的跟标杆一样，count++
2) 如果不相等，--count，若此时count为0，则把当前值置为标杆，count为1
重复1), 2)即可，最后那个标杆即为最流行搜索词。
代码简单的我不能相信，以至于我觉得我肯定理解错误题目的意思了，不管怎么样上下
代码：
1 // Get the most popular searching keyword in Google. :)
2 template<typename T>
3 T get_most_popular_keyword(const T *list, int size) {
4 T result = list[0];
5 int count = 0;
6
7 for (int i=0; i<size; i++) {
8 if (list[i] == result)
9 count++;
10 else {
11 if (--count == 0) {
12 count = 1;
13 result = list[i];
14 }
15 }
16 }
17
18 return result;
19 }