本題目出自
@陳利人問(wèn)題：
#Google面試題#給你一天的Google搜索日志，你怎么設(shè)計(jì)算法找出是否有一個(gè)搜索詞，它出現(xiàn)的頻率占所有搜索的一半以上？如果肯定有一個(gè)搜索詞占大多數(shù)，你能怎么提高你的算法找到它？再假定搜索日志就是內(nèi)存中的一個(gè)數(shù)組，能否有O(1)空間，O(n)時(shí)間的算法？
剛看到這個(gè)題目的時(shí)間嚇壞了，好難啊，無(wú)從下手啊，為自己的之上捉急啊。。下班的班車(chē)上開(kāi)始想這個(gè)問(wèn)題，開(kāi)始分析，其實(shí)這個(gè)搜索日志就是一個(gè)搜索詞的集合嘛，甭管它有多大，總可以分成若干堆吧。既然這個(gè)搜索詞超過(guò)一半，那么在這若干堆中分別找出來(lái)最流行的詞中，也應(yīng)該占一半吧。（這個(gè)應(yīng)該沒(méi)有理解錯(cuò)吧。）
這個(gè)時(shí)候我想可以把問(wèn)題轉(zhuǎn)換成一個(gè)整數(shù)數(shù)組，其中有個(gè)整數(shù)出現(xiàn)的次數(shù)超過(guò)一半，找出這個(gè)整數(shù)就OK了吧。要找出這個(gè)數(shù)組中出現(xiàn)次數(shù)超一半的值，本身這個(gè)算法應(yīng)該很簡(jiǎn)單，但是O(1)空間和O(n)的時(shí)間復(fù)雜度，還是有點(diǎn)傷腦筋的。。:(，內(nèi)存又不貴，為啥O(1)啊。。
因?yàn)槟莻€(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)一半，我們可以想象一下，把那個(gè)數(shù)字標(biāo)成1，其它的都是-1，把所有的數(shù)字加起來(lái)肯定大于0，對(duì)吧？因?yàn)槌^(guò)一半嘛。。這個(gè)時(shí)候靈光乍現(xiàn)，用一個(gè)標(biāo)桿來(lái)標(biāo)志潛在的那個(gè)搜索詞，一個(gè)整數(shù)count表示它出現(xiàn)的次數(shù)（準(zhǔn)確的說(shuō)不是它的次數(shù)，后面會(huì)解釋?zhuān)闅v整個(gè)數(shù)組
1) 如果當(dāng)前的跟標(biāo)桿一樣，count++
2) 如果不相等，--count，若此時(shí)count為0，則把當(dāng)前值置為標(biāo)桿，count為1
重復(fù)1), 2)即可，最后那個(gè)標(biāo)桿即為最流行搜索詞。
代碼簡(jiǎn)單的我不能相信，以至于我覺(jué)得我肯定理解錯(cuò)誤題目的意思了，不管怎么樣上下
代碼：
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 }