給你一天的Google搜索日志，你怎么設計算法找出是否有一個搜索詞，它出現的頻率占所有搜索的一半以上？如果肯定有一個搜索詞占大多數，你能怎么提高你的算法找到它？再假定搜索日志就是內存中的一個數組，能否有O(1)空間，O(n)時間的算法？
最多連續數的子集之參考答案
題目：
給一個整數數組， 找到其中包含最多連續數的子集，比如給：15, 7, 12, 6, 14, 13, 9, 11，則返回: 5:[11, 12, 13, 14, 15] 。最簡單的方法是sort然后scan一遍，但是要o(nlgn)，有什么O(n)的方法嗎？
分析：
我們先來學習一種叫做并查集的數據結構。
并查集（Disjoint set或者Union-find set）是一種簡單的用途廣泛的算法和數據結構。并查集是若干個不相交集合，能夠實現較快的合并和判斷元素所在集合的操作，應用很多，如其求無向圖的連通分量個數等。
并查集可以方便地進行以下三種操作：
1、Make_Set(x) 把每一個元素初始化為一個集合
初始化后每一個元素的父親節點是它本身，每一個元素的祖先節點也是它本身（也可以根據情況而變）。
2、Find_Set(x) 查找一個元素所在的集合
查找一個元素所在的集合，其精髓是找到這個元素所在集合的祖先。這個才是并查集判斷和合并的最終依據。
判斷兩個元素是否屬于同一集合，只要看他們所在集合的祖先是否相同即可。
合并兩個集合，也是使一個集合的祖先成為另一個集合的祖先，具體見示意圖。
3、Union(x,y) 合并x,y 所在的兩個集合
合并兩個不相交集合操作很簡單：
利用Find_Set找到其中兩個集合的祖先，將一個集合的祖先指向另一個集合的祖先。如圖
并查集的優化：
1、Find_Set(x)時 路徑壓縮
尋找祖先時我們一般采用遞歸查找，但是當元素很多亦或是整棵樹變為一條鏈時，每次Find_Set(x)都是O(n)的復雜度，有沒有辦法減小這個復雜度呢？
答案是肯定的，這就是路徑壓縮，即當我們經過"遞推"找到祖先節點后，"回溯"的時候順便將它的子孫節點都直接指向祖先，這樣以后再次Find_Set(x)時復雜度就變成O(1)了，如下圖所示；可見，路徑壓縮方便了以后的查找。
2、Union(x,y)時 按秩合并
即合并的時候將元素少的集合合并到元素多的集合中，這樣合并之后樹的高度會相對較小。
有了背景知識，我們來看如何利用它來解決這個問題。
首先，Make_Set(x)將每個元素變成一個并查集，然后掃描，Union(x-1, x)，Union(x, x+1)。
接下來的問題是怎么快速找到x-1,x+1的位置？那么需要引入查找為常數復雜度的哈希表。
其他網友建議的解決方案
網友Mike建議 :
用一個map，它的key是一個起始的數字，value是這個起始數字起連續的個數。這樣這個數組遍歷一遍下來，只要map維護好了，自然就能得到最長的連續子串了，并且算法復雜度應該是O(n)。（不考慮map函數實現的復雜度）
前面說了維護好map就可以了，那么怎么來維護這個map呢？
取出當前的整數，在map里看一下是否已經存在，若存在則直接取下一個，不存在轉2 (為什么要看是否已經存在，因為題目沒有說不會有重復的數字。) 查看下map里面當前數字的前一個是否存在，如果存在，當前的最長長度就是前一個最長長度+1 查看下map里面當前數字的后一個是否存在，如果存在，那么就將以下一個數字開始的子串的最后一個更新下，因為本來沒有連上的2個子串，因為當前數字的出現連起來了 接著再看下前面數字是否存在，如果存在，就更新以這個數字結尾的子串的第一個數字的連續子串長度，原因同上。
算法就是如上所示了，我們拿例子演練一遍。
- 首先給定15，這個時候map里面沒有15也沒有14和16，那么這個執行完了之后map是map[15] = 1;
- 然后遇到7，同上，也沒有6，7和8，所以執行玩了之后變成map[7]=1, map[15]=1;
- 12同上，map[7]=1, map[12]=1, map[15]=1;
- 接下來是6，6就不一樣了，因為7存在的，所以執行上面第3步之后，map[6]=2,map[7]=2,map[12]=1,map[15]=1;
- 14的情況跟6一樣，結果是map[6]=2,map[7]=2,map[12]=1,map[14]=2,map[15]=2;
- 13的情況相對復雜一些，因為12和14都存在了 ，所以它會執行以上1，2，3，4的所有4步：首先12存在，所以13的最長子串是2，14存在，所以會更新到14起始的最后一個數字的最長長度，這里就 是15的長度=它自己的加上13的長度，也就是4，同時我們把13的長度也改成4，最后因為12存在，我們要更新以12結尾的連續子串的開始處，本例中就 是12自己，12對應更新成4。
- 最后是11，11的前面一個數字不存在，后一個數字存在，也就是要執行以上1，3，第3步結束的時候已經是11和15都更新成5了。最后的結果也就是5，并且是從11起始的。
網友xd_jackfeng建議：
設置一個bitmap，初始值為0，如果出現則設置為1，這樣看有多少個1連續就可以了。
