网易笔试 求最长的连续整数片段长度

缘起

给你100,2,1,3 这样的正整数序列, 要你求最长的连续正整数的片段的长度. 答案是3（因为有1 2 3）

注意，如果是要求数字还相邻才能算连续的话, 则就是0，不过这样的话, 问题就很平凡了——O(N)时间内解决（逐个扫描，发现更大的就更新），不过这里也给出相应的算法（源码1）.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "stdafx.h"
#include <stdio.h>

int a[]={10,21,45,22,7,2,1,2,3,4,5,6,16,17,100,201,20,101};

int main()
{
	int _max=1,_maxindex=0; // 最大连续正整数片段的长度和起始索引
	for (int i =0,len;i<sizeof(a)/sizeof(int);i++)
	{
		len =1;
		while(a[i]+1==a[i+1]) i++,len++; // 则最后 a[i]+1!=a[i+1]
		if (len>_max)_max = len,_maxindex = i-len+1;
	} // 复杂度是O(N)
	printf("最长连续正整数片段起于%d, 长%d\n", _maxindex, _max);
	return 0;
}

​ 源码1

那第一个问题怎么解决呢? 就是 10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101 这样的数组，16,17,18,19,20,21,22 则答案是7.

有人会说，可以这样呀~ 一张哈希表, hash[200],hash[i]=true表示i出现了，hash[i]=false表示i没有出现，则从左至右扫描整个数组，逐个将数组元素插入哈希表, 插入之后就开始左右扩展扫描，直至无法扩展为止，然后更新max. 但是这样的话，算法的复杂度最坏是O(N^2)的（比如测试数据就是N个连续的自然数）. 这显然不行. 怎么办呢? 关键就是注意——只需要每个区间的边界点维护这个区间的长度信息就可以了. 那么新加入哈希表一个点，如果hash[a[i]]=true了，则不用管（已经存在了），如果不存在，则只需要往左看看，往右看看，如果能连上，马上更新区间长度信息. 然后再更新max信息. 整个算法过程如下图所示

这样，算法的复杂度才是O(n)的——关键就是在区间的边界点上维护了区间的范围信息（空间换时间）.

算法实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "stdafx.h"
#include <stdio.h>

int a[]={10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101},b[200],_max=1, _maxinit=0,flag[200]; // b[i]表示i记录了它作为边界点的片段的长度, flag[i]为0表示它是单点，1表示i作为片段的右边界点, 2表示i作为片段的左边界点.
bool h[200]; // h[i]=true表示i在前面的扫描中已经出现过了

int main()
{
	for (int i = 0,len, init; i<sizeof(a)/sizeof(int);i++)
	{
		if (h[a[i]]) continue; // 如果已经出现过了
		h[a[i]] = true;
		if (h[a[i]-1]) // 如果左边有, 则a[i]-1一定作为它所在片段的右端点(注意，单点片段的单点既是该单点片段的左端点又是右端点)
		{
			flag[a[i]] = 1; // 右端点
			flag[a[i]-b[a[i]-1]] = 2; // 左端点
			len = b[init = a[i]-b[a[i]-1]] = b[a[i]] = b[a[i]-1]+1; // a[i]成为新的右端点,维护该区间原本的左端点
		}
		if (h[a[i]+1]) // 如果右边有
		{
			if (flag[a[i]] == 1) // 如果它作为某个区间的右边界点的话,则说明a[i]已经将两个片段连接起来了,则就不需要再管b[a[i]]了, 而要去维护原先两个被连接起来的边界点
			{
				flag[a[i]-b[a[i]-1]] = 2; // 左端点
				flag[a[i]+b[a[i]+1]] = 1; // 右端点
				len = b[a[i]+b[a[i]+1]] = b[init = a[i]-b[a[i]]+1] = b[a[i]+1]+b[a[i]];
			}
			else // 如果a[i]不作为某个区间的右边界的话, 则a[i]将作为a[i]+1,...a[i]+b[a[i]+1] 这个区间的新的左边界
			{
				flag[a[i]] = 2; // 左端点
				flag[a[i]+b[a[i]+1]] = 1; // 右端点
				len = b[init = a[i]] = b[a[i]+b[a[i]+1]] = b[a[i]+1]+1;
			}
		}
		else if(!flag[a[i]])// 右边没有, 左边也没有, 则就是一个单点片段
		{
			flag[a[i]] = 0; // 单点
			len = b[init = a[i]] = 1;
		}
		if (len > _max)
		{
			_max = len;
			_maxinit = init;
		}
	}
	printf("最长连续正整数片段的长度是%d, 起始于%d\n", _max, _maxinit);
	return 0;
}

其实上面算法的关键就是插入哈希表的时候要O(1)时间维护涉及的片段的左右端点上附带的片段信息，并且O(1)时间更新_max和_maxinit.

最后说一句，当然，还有一种算法是排序之后，再使用源码1的算法, 这样也是可以的，但是复杂度是O(NlogN)的了. 还是没有这里给出的算法性能好.