本題目出自
@陳利人問題：
#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 }