输入 n 个未排序的数字组成的数组，求排序之后相邻元素之间最

[问答题]

输入 n 个未排序的数字组成的数组，求排序之后相邻元素之间最大的差值。

要求：算法的时间复杂度为 O(n) ，数字取值区间为 [-2^32,2^32-1] 。

输入数据有两行，第一行表示数组的数字量 n ，第二行表示数组

4,1,7,5

输出

雪斗无知

//不太明白桶方法为什么那么除，不过既然只要求时间复杂度，那可以偷空间的懒
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int[] array = new int[n];
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i = 0;i<n;i++){
                int a = sc.nextInt();
                array[i] = a;
                max = Math.max(max,a);
                min = Math.min(min,a);
            }
            boolean[] array2 = new boolean[max-min+1];
            for(int i = 0;i<n;i++){
                array2[array[i]-min] = true;
            }
            int count = 0;
            int maxCount = 0;
            for(int i = 0;i<array2.length;i++){
                if(array2[i]==false){
                    count++;
                    maxCount = Math.max(count,maxCount);
                }else{
                    count = 0;
                }
            }
            if(n>=2){
                maxCount++;
            }
            System.out.println(maxCount);
        }
    }
}

发表于 2017-03-17 16:26:07 回复(1)

Paraia

https://juejin.im/post/5a44acaa6fb9a0451d41c850 这篇文章讲到位了

发表于 2019-03-15 16:45:41 回复(0)

牛客823431号

用一个新数组arr长度为原来数组最大值，然后对于原来数组依次求余最大值然后放入arr中。这样得到的arr就是有序的但是内存不一定连续，然后遍历找最大值即可。

发表于 2017-08-26 10:53:41 回复(3)

智能风暴来袭

public class Main{
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();	
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}	
		Arrays.sort(arr);	
		int max = 0;
		for (int i = 1; i < n; i++) {
			max = Math.max(max,arr[i]-arr[i-1]);
		}
		System.out.println(max);
	}
}

发表于 2017-08-07 11:52:31 回复(4)