一个公司的Java面试题

public static void main(String[] args)
    {
       
       int[] a= {1,5,3,2,4,6};     
       Arrays.sort(a);
       int num = (a[0]+a[a.length-1])*a.length/2;
       int num1 =0;
       for(int i=0;i<a.length;i++)
       {
           num1+=a[i];
       }
       if(num ==  num1)
       {
            System.out.println("连续");
       }
       else
       {
            System.out.println("不连续");
       }
    }

	public static void main(String []args){
				
			int[] a= {1,3,5,2,4,8};
			int[] b= {6,3,2,5,4,1};
			
			Arrays.sort(a);
			Arrays.sort(b);
			sort(a);
			sort(b);
			
	}
	
	public static void sort(int a[]){
		boolean flag = false;
		for (int i = 0; i < a.length; i++) {
				if(i != a.length - 1){
					if(a[i]+1 != a[i+1]){
						flag = true;
					}
				}
		}
		if(flag){
			System.out.println("该数组不连续");
		}else{
			System.out.println("该数组连续");
		}
	}

为什么??

这个非常精妙，可否解释下?

排序中判断

精辟！

精妙啥，这个思路就是递增数组求和，可是数组是可以重复的！！
如果去掉这个前提条件，上面兄弟的“max-min+1 == length”岂不是来得更简单

kimmking兄的算法是不是没考虑数组重复的情况啊？否则怎么就“array的长度是不是m-n+1，不是就return false”

赞同kimmking的观点，附上验证结果

public class Test
{
    public static void main(String[] args)
    {
        // 准备数组
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 100000; i++)
        {
            list.add(i);
        }
        Integer[] array = (Integer[])list.toArray(new Integer[0]);
        
        long beginTime = System.nanoTime();
        System.out.println(isContinuousArray(array)?"数组连续":"数组不连续");
        long endTime1 = System.nanoTime();
        System.out.println("耗时:" + (endTime1 - beginTime));
        System.out.println(isContinuousArrayUseSet(array)?"数组连续":"数组不连续");
        long endTime2 = System.nanoTime();
        System.out.println("耗时:" + (endTime2 - endTime1));
    }
    
    /**
        先一次循环数组array，拿到最大值m和最小值n。 
        然后看array的长度是否大于等于m-n+1，不是就return false。 
        然后创建一个新数组bucket[m-n+1], 
        对于数组array中的每一个数x，令bucket[x-n]=1， 
        定义y =1 
        最后循环一遍bucket，y = y&bucket[i];如果y=0，return false 
        否则，return true。 
     */
    public static boolean isContinuousArray(Integer[] array)
    {
        if (null == array || 0 == array.length)
        {
            return false;
        }
        int min = array[0];
        int max = array[0];
        
        for (int i : array)
        {
            if (i > max)
            {
                max = i;
            }
            
            if (i < min)
            {
                min = i;
            }
        }
        
        if (max - min + 1 > array.length)
        {
            return false;
        }
        
        int[] temp = new int[max - min + 1];
        
        for (int i : array)
        {
            temp[i-min] = 1;
        }
        
        for (int i : temp)
        {
            if (i != 1)
            {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 使用Set过滤掉重复数据
     * add过程中set会查找是否存在相同的元素，这个过程会占一定的效率
     */
    public static boolean isContinuousArrayUseSet(Integer[] array)
    {
        if (null == array || 0 == array.length)
        {
            return false;
        }
        
        int min = array[0];
        int max = array[0];
        
        Set<Integer> set = new HashSet<Integer>();
        
        for (int i : array)
        {
            if (i > max)
            {
                max = i;
            }
            
            if (i < min)
            {
                min = i;
            }
            
            set.add(i);
        }
        
        return max - min + 1 == set.size();
    }
}

数组连续
耗时:3337193
数组连续
耗时:80879403

{123,4}这样的数组行不