77 找出最大连续自然数个数[Longest Consecutive Sequence in an Unsorted Array]

【本文链接】

http://www.cnblogs.com/hellogiser/p/Longest-Consecutive-Sequence-in-an-Unsorted-Array.html

【题目】

一个无序自然数数组，比如[100,2,1,3]求在0(n)时间复杂度内求出最大的连续自然数个数：输出应该是3

【分析】

方法一：排序
可以采用一些排序方法比如基数排序、桶排序、记数排序等先进行排序。然后遍历一遍所有元素即可。当前这些排序有一些限制条件的。

方法二：维持一个hash表
维持一个hash表，大小为最大整数。遍历一次数组，用hash表记录出现在原始数组中的数。
然后设置四个个指示变量start，end，length，bestLength = 0。初始，start = end = 数组中第一个数，length = 1。然后不断执行下列操作：
end = end + 1.然后在hash表中寻找end，如果能够找到，说明end存在原始数组中。一直到找不到end位置。
然后设置length = end - start。如果length大于bestLength，则更新：bestLength = length。
然后将start和end都设置为刚才为查找到的那个数，length = 1，接着重复上面的操作，最终的bestLength 便是最大的连续自然数个数。
由于hash的查找等操作都能在O(1)时间复杂度内完成，因此hash方法能够满足O(n)时间复杂度。

方法三：位图
用位图。类似方法二。
位图大小和最大的整数有关。位图中每一位为0或者1。位图某个位置index上为1表示index出现在原始数组中，反之不存在。遍历一遍原始数组建立位图之后，采用类似方法二中遍历hash表的方法遍历位图，找出最大的连续自然数个数。
位图的方法存在一个问题就是：可能最大的数很大，但是数的数目有很小，这时候要申请的位图的空间依然是很大，时候复杂度不是O(n)。

【参考】

http://stackoverflow.com/questions/7453248/longest-consecutive-sequence-in-an-unsorted-array

http://stackoverflow.com/questions/5415305/finding-contiguous-ranges-in-arrays

http://blog.csdn.net/xiajun07061225/article/details/8706276

http://www.cnblogs.com/sooner/p/3279429.html