输入 n 个未排序的数字组成的数组,求排序之后相邻元素之间最大的差值。
要求:算法的时间复杂度为 O(n) ,数字取值区间为 [-2^32,2^32-1] 。
输入数据有两行,第一行表示数组的数字量 n ,第二行表示数组
4
4,1,7,5
输出
3
//不太明白桶方法为什么那么除,不过既然只要求时间复杂度,那可以偷空间的懒 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); } } }
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); } }