【实习笔试面试题】2013网易互联网实习笔试算法题-找出最大连续自然数个数.doc

【实习笔试面试题】2013网易互联网实习笔试算法题-找出最大连续自然数个数找出最大连续自然数个数以下参考答案为自己搜集网上资料以及同学讨论所得，如有错误，还请指出。欢迎来信交流！题目： 一个无序自然数数组，比如100,2,1,3求在0(n)时间复杂度内求出最大的连续自然数个数：输出应该是3思路：方法一：排序可以采用一些排序方法比如基数排序、桶排序、记数排序等先进行排序。然后遍历一遍所有元素即可。当前这些排序有一些限制条件的。方法二：维持一个hash表维持一个hash表，大小为最大整数。遍历一次数组，用hash表记录出现在原始数组中的数。然后设置四个个指示变量start，end，length，bestLength = 0。初始，start = end = 数组中第一个数，length = 1。然后不断执行下列操作：end = end + 1.然后ziahash表中寻找end，如果能够找到，说明end存在原始数组中。一直到找不到end位置。然后设置length = end - start。如果length大于bestLength，则更新：bestLength = length。然后将start和end都设置为刚才为查找到的那个数，length = 1，接着重复上面的操作，最终的bestLength 便是最大的连续自然数个数。方法三：位图用位图。类似方法二。位图大小和最大的整数有关。位图中每一位为0或者1。位图某个位置index上为1表示index出现在原始数组中，反之不存在。遍历一遍原始数组建立位图之后，采用类似方法二中遍历hash表的方法遍历位图，找出最大的连续自然数个数。方法四：维持两个hash表维持两个hash表tables：Start表，其中的条目都是如下格式(start-point,length)，包含的某个连续序列起始数以及序列长度。End表，其中的条目都是如下格式(end-point,length)，包含的某个连续序列结束数以及序列长度。扫描原始数组，做如下操作：对于当前值value，判断value + 1是否存在于start表中。如果存在，删除相应的条目，创建一个新条目(value,length + 1)，同时更新end表相应条目，结束数不变，该对应长度加一。判断value - 1是否存在于end表中。如果存在，删除相应的条目，创建一个新条目(value,length + 1)，同时更新start表相应条目，开始数不表，该对应长度加一。如果在两个表中都存在，则合并两个已经存在的连续序列为一个。将四个条目删除，新建两个条目，每两个条目代表一个连续序列。如果都不存在，则只需要在两个表中创建一个新的长度为1的条目。一直这样等到数组中所有元素处理完毕，然后扫描start表寻找length值最大的那个即可。这里要达到O(n)时间复杂度，start表和end表都用hash表实现，而且必须满足相关操作查找/添加/删除能够在O(1)时间复杂度内完成。实例分析：int input = 10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101;初始化状态：Start table：End table：开始遍历数组：10：两个数组中都不存在，添加条目。Start table：(10,1)End table：(10,1)21：两个数组中都不存在，添加条目。Start table：(10,1)，(21,1)End table：(10,1)，(21,1)45：两个数组中都不存在，添加条目。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：两个数组中都不存在，添加条目。Start table：(10,1)，(21,2)，(45,1)，(7,1)End table：(10,1)，(22,2)，(45,1)，(7,1)2：两个数组中都不存在，添加条目。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：两个数组中都不存在，添加条目。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：两个数组中都不存在，添加条目。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：两个数组中都不存在，添加条目。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：两个数组中都不存在，添加条目。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