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