一个数组序列,元素取值可能是0--65535中的任意一个数,相同数值不会重复出现。0可以重复出现。当从该数组序列中随机选取5个数值,判断这5个数值是否连续相邻。
需要注意4点:
1.) 5个数值允许是乱序的,例如{8,7,5,0,6}
2.) 0可以通配任意数值,例如{8,7,5,0,6}中的0可以通配成9或4
3. )0可以多次出现
4. )全0算连续,只有一个非0算连续
1)如果没有0的存在,要组成连续的数列,最大值和最小值的差距必须是4
2)存在0的情况下,只要最大值和最小值的差距小于4就可以了,
所以应找出数列中非0的最大值和非0的最小值,时间复杂度为O(n)
package JBArray; public class IsContinuous { /** * 如果没有0的存在,要组成连续的数列,最大值和最小值的差距必须是4 * 存在0的情况下,只要最大值和最小值的差距小于4就可以了, * 所以应找出数列中非0的最大值和非0的最小值,时间复杂度为O(n) * @param a * @return */ private static boolean IsContinous(int[] a) { int len = a.length; int min = -1, max= -1; for(int i=0; i<len; i++){ if(a[i] != 0){ if(min>a[i] || min==-1) min = a[i]; if(max<a[i] || max==-1) max = a[i]; } }//for if(max - min > len-1) return false; else return true; } public static void main(String[] args) { int a[] = {8,7,5,0,6}; if(IsContinous(a)){ System.out.println("{8,7,5,0,6}相邻"); }else System.out.println("{8,7,5,0,6}不相邻"); } }