一个整数数组，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现；0是例外，可以反复出现。设计一个算法，判断这个数组中的元素是否连续相邻。需要注意以下4点：
（1）数值允许是乱序的，如 8 7 5 0 6。
（2）0可以通配任意数值，如8 7 5 0 6中的0可以通配成9或者4.
（3）0可以多次出现。
（4）全0算连续，只有一个非0算连续。
思路分析：
如果没有0的存在，要组成连续的数列，最大值和最小值的差距必须是n-1；存在0的情况下，只要最大值可最小值的差距小于n-1就可以了，缺失的数值可以用0通配。所以找出数列中非0的最大值和非0的最小值，时间复杂度为O(n)。如果非0最大-非0最小+1<n，即非0最大-非0最小<=n-1，则这n个数值连续相邻。否则，不连续相邻。因此，总体复杂度为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 |
#include "stdafx.h"#include<stdio.h>bool
IsContinuous(int* a, int
n){ if
(a == NULL || n <= 0) return
false; int
min = a[0], max = a[0]; for
(int i = 1; i < n; i++) { if
(a[i] != 0) { if
(min>a[i]) min = a[i]; if
(max < a[i]) max = a[i]; } } if
(max - min>n - 1) return
false; else return
true;}int
main(){ int
array[] = { 8, 7, 5, 0, 6 }; int
len = sizeof(array) / sizeof(array[0]); if
(IsContinuous(array, len)) printf("数组连续相邻\n"); else printf("数组不连续相邻\n"); getchar(); return
0;} |
效果如图：
如何判断一个数组中的数值是否连续相邻,布布扣,bubuko.com
原文：http://www.cnblogs.com/cysolo/p/3590776.html