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