请设计一个复杂度为O(n)的算法,计算一个未排序数组中排序后相邻元素的最大差值。
给定一个整数数组A和数组的大小n,请返回最大差值。保证数组元素个数大于等于2小于等于500。
测试样例:
[9,3,1,10],4
返回:6
import java.util.Arrays;import java.util.Scanner;
//找出相差最大的相邻元素的差
import java.util.*; public class MaxDivision { public int findMaxDivision(int[] A, int n) { // 计数排序,时间复杂度O(max-min+1),空间复杂度O(max-min+1),达不到O(n) int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int i = 0; i < A.length; i ++) { max = max > A[i] ? max : A[i]; min = min < A[i] ? min : A[i]; } boolean[] flag = new boolean[max - min + 1]; for (int i = 0; i < n; i ++) { flag[A[i] - min] = true; } int res = Integer.MIN_VALUE; int cur = 0, pre = 0; while ( ! flag[pre]) { cur ++; pre ++; } for (; cur < flag.length; cur ++) { if(flag[cur]) { res = res > cur - pre ? res : cur - pre; pre = cur; } } return res; } }