网易2013笔试(C++)编程题
最后一道大题：
给一个未经排序的自然数组。找出数组中最大的连续自然数序列的个数。如给定[100,2,1,3]。最大 连续自然数序列因为[1,2,3]。返回结果为3。
要求算法复杂度为O(n)。

感觉好难，想了好久没想出来。求各位大神知道 网易笔试 算法
[解决办法]
用hash就行了。
简单点说，就是开一个N的数组，bool b[N];
然后循环一次序列a[N], 让b[a[i]]=1
最后你再遍历一次b数组就得到结果了。
用了两次遍历复杂度是O(N)
[解决办法]

引用:

用hash就行了。
简单点说，就是开一个N的数组，bool b[N];
然后循环一次序列a[N], 让b[a[i]]=1
最后你再遍历一次b数组就得到结果了。
用了两次遍历复杂度是O(N)

++ 用bitmap
[解决办法]

引用:

Quote: 引用:

用hash就行了。
简单点说，就是开一个N的数组，bool b[N];
然后循环一次序列a[N], 让b[a[i]]=1
最后你再遍历一次b数组就得到结果了。
用了两次遍历复杂度是O(N)

++ 用bitmap

问题是题目里给的自然序列中的最大数可能远大于这个序列的长度，那这个bitmap的大小怎么确定？难道是动态生成？
[解决办法]
感觉很难做到O(n)，至少每个数要过一遍吧，这样每个数的处理至多是O(1)，除了hash，没想到更好的。
[解决办法]
基于3#的思路。

数组b可以做的复杂一些，分几个级别，比如第一个级别1-99999999 100000000-199999999 ....
第二个级别1- 9999 10000-19999 ... 第三个级别 1-99 100-199 ...
这样就能快速定位，也节省内存（需要的时候再分配二三级）。

每个位置不存bool值存指针，指针里面存计数，每次插入数字时判断前后有没有数字，有的话指针设置成一样的。合并前后计数再+1

每次操作的时候跟已保存的最大序列数字比较。

这样就保证只遍历原数据1次，就能得到最终结果。