找出最大連續(xù)自然數(shù)個數(shù)
搜集者：江南煙雨
E-Mail：xiajunhust@gmail.com
本題為網(wǎng)易互聯(lián)網(wǎng)暑期實習(xí)生筆試算法題。
憑記憶記錄下來的題目，如違反網(wǎng)易版權(quán)請郵件聯(lián)系，本人會刪除。
以下參考答案為自己搜集網(wǎng)上資料以及同學(xué)討論所得，如有錯誤，還請指出。歡迎來信交流！
題目：
一個無序自然數(shù)數(shù)組，比如[100,2,1,3]求在0(n)時間復(fù)雜度內(nèi)求出最大的連續(xù)自然數(shù)個數(shù)：輸出應(yīng)該是3
思路：
方法一：排序
可以采用一些排序方法比如基數(shù)排序、桶排序、記數(shù)排序等先進行排序。然后遍歷一遍所有元素即可。當(dāng)前這些排序有一些限制條件的。
方法二：維持一個hash表
維持一個hash表，大小為最大整數(shù)。遍歷一次數(shù)組，用hash表記錄出現(xiàn)在原始數(shù)組中的數(shù)。
然后設(shè)置四個個指示變量start，end，length，bestLength = 0。初始，start = end = 數(shù)組中第一個數(shù)，length = 1。然后不斷執(zhí)行下列操作：
end = end + 1.然后ziahash表中尋找end，如果能夠找到，說明end存在原始數(shù)組中。一直到找不到end位置。
然后設(shè)置length = end - start。如果length大于bestLength，則更新：bestLength = length。
然后將start和end都設(shè)置為剛才為查找到的那個數(shù)，length = 1，接著重復(fù)上面的操作，最終的bestLength 便是最大的連續(xù)自然數(shù)個數(shù)。
由于hash的查找等操作都能在O(1)時間復(fù)雜度內(nèi)完成，因此hash方法能夠滿足O(n)時間復(fù)雜度。
方法三：位圖
用位圖。類似方法二。
位圖大小和最大的整數(shù)有關(guān)。位圖中每一位為0或者1。位圖某個位置index上為1表示index出現(xiàn)在原始數(shù)組中，反之不存在。遍歷一遍原始數(shù)組建立位圖之后，采用類似方法二中遍歷hash表的方法遍歷位圖，找出最大的連續(xù)自然數(shù)個數(shù)。
位圖的方法存在一個問題就是：可能最大的數(shù)很大，但是數(shù)的數(shù)目有很小，這時候要申請的位圖的空間依然是很大，時候復(fù)雜度不是O(n)。
方法四：維持兩個hash表
維持兩個hash表tables：
Start表，其中的條目都是如下格式(start-point,length)，包含的某個連續(xù)序列起始數(shù)以及序列長度。
End表，其中的條目都是如下格式(end-point,length)，包含的某個連續(xù)序列結(jié)束數(shù)以及序列長度。
掃描原始數(shù)組，做如下操作：
對于當(dāng)前值value，
判斷value + 1是否存在于start表中。
如果存在，刪除相應(yīng)的條目，創(chuàng)建一個新條目(value,length + 1)，同時更新end表相應(yīng)條目，結(jié)束數(shù)不變，該對應(yīng)長度加一。
判斷value - 1是否存在于end表中。
如果存在，刪除相應(yīng)的條目，創(chuàng)建一個新條目(value,length + 1)，同時更新start表相應(yīng)條目，開始數(shù)不表，該對應(yīng)長度加一。
如果在兩個表中都存在，則合并兩個已經(jīng)存在的連續(xù)序列為一個。將四個條目刪除，新建兩個條目，每兩個條目代表一個連續(xù)序列。
如果都不存在，則只需要在兩個表中創(chuàng)建一個新的長度為1的條目。
一直這樣等到數(shù)組中所有元素處理完畢，然后掃描start表尋找length值最大的那個即可。
這里要達到O(n)時間復(fù)雜度，start表和end表都用hash表實現(xiàn)，而且必須滿足相關(guān)操作查找/添加/刪除能夠在O(1)時間復(fù)雜度內(nèi)完成。
實例分析：
int[] input = {10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101};
初始化狀態(tài)：
Start table：{}
End table：{}
開始遍歷數(shù)組：
10：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)}
End table：{(10,1)}
21：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,1)}
End table：{(10,1)，(21,1)}
45：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,1)，(45,1)}
End table：{(10,1)，(21,1)，(45,1)}
22：22-1=21存在于end表中需要進行更新。
Start table：{(10,1)，(21,2)，(45,1)}
End table：{(10,1)，(22,2)，(45,1)}
7：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)}
2：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)}
67：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)}
19：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
13：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
End table：{(10,1)，(22,2)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
45：兩個數(shù)組中都不存在，添加條目。
Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,1)}
12：12+1=13存在start表中，更新。
Start table：{(10,1)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(12,2)}
End table：{(10,1)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)，(13,2)}
11：11+1=12都存在，合并。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,1)}
18：18+1=19存在start表中，更新。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)}
16：都不存在，添加條目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(18,2)，(16,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,2)，(16,1)}
17：都存在，合并。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)}
100：都不存在，添加條目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)}
201：都不存在，添加條目。
Start table：{(10,4)，(21,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(16,4)，(100,1)，(201,1)}
End table：{(13,4)，(22,2)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(19,4)，(100,1)，(201,1)}
20：都存在，合并。
Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}
End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)}
101：都存在，合并。
Start table：{(10,4)，(16,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(101,1)}
End table：{(13,4)，(22,7)，(45,1)，(45,1)，(7,1)，(2,1)，(67,1)，(100,1)，(201,1)，(201,1)}
最后搜索start表，找到length值最大的，為7.連續(xù)自然數(shù)序列是：（16,17,18,19,20,21,22）.
結(jié)束。
參考資料：
|
