WF4.0实战(十三):解微软一道面试题
题目:一个整数数列,元素取值可能是0—65535中的任意一个数,相同数值不会重复出现。0是例外,可以反复出现。 请设计一个算法,当你从该数列中随意选取5个数值,判断这5个数值是否连续相邻。 注意: 1、5个数值允许是乱序的。比如: 8 7 5 0 6; 2、0可以通配任意数值。比如:8 7 5 0 6 中的0可以通配成9或者4; 3、0可以多次出现; 4、复杂度如果是O(n2)则不得分。 分析:通过分析你可以发现,题目只要满足:除0之外的最大数减去除0之外的最小数小于等于4就行了。 故只要通过一个循环就5个数字中除0之外的最大数和最小数。求差之后与4做个比较就行了。伪代码如下: 1 public booleanisContiguous( int []array) 2 { 3 int min =- 1 ; 4 int max =- 1 ; 5 for ( int i = 0 ;i < array.length;i ++ ) 6 { 7 if (array[i] != 0 ) 8 { 9 if (min ==- 1 || min > array[i]) 10 { 11...