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

时间:2021-03-25 03:12:48

【本文链接】

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://*.com/questions/7453248/longest-consecutive-sequence-in-an-unsorted-array

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

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

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