給定一個整型數(shù)組arr，返回排序后的相鄰兩數(shù)的最大差值
舉例：
arr = [9,3,1,10]曙咽。如果排序蛔趴，結(jié)果為[1,3,9,10]，9和3的差為最大差值例朱。故返回6孝情。
arr = [5,5,5,5]。返回0洒嗤。
這道題是阿里往年的一道面試題箫荡，據(jù)說把ACM World Final選手都難住了，因為正式的ACM比賽中判題系統(tǒng)往往不會僅讓O(n)的算法AC渔隶，而卡住O(nlogn)的算法羔挡，所以ACM選手普遍缺乏對O(logn)那部分復(fù)雜度的優(yōu)化訓(xùn)練。
而本題如果用普通的比較排序方法來實現(xiàn)间唉，時間復(fù)雜度是O(nlogn)绞灼，這并不是一個能讓面試官滿意的答案。
要做到O(n)的時間復(fù)雜度呈野，考慮利用桶排序的思想低矮，不過不是直接進行排序。
假設(shè)arr的長度為n被冒，我們準備n+1個桶军掂，桶號 0 ~ n。對于arr中的任意一個數(shù)num姆打，利用映射函數(shù)(num - min) * n / (max - min)將其映射到對應(yīng)的桶中良姆。通過這種映射，min會單獨占據(jù)0號桶幔戏，max會單獨占據(jù)n號桶玛追，當把所有的n個數(shù)放進n+1個桶中，中間必然有個桶是空的。因此痊剖，排序后的最大差值只可能來自某個非空桶中的最小值減去前一個非空桶中的最大值韩玩。
具體過程請參看如下代碼：
public class ArrayMaxGap {
/**
* 映射函數(shù)，將數(shù)組元素映射到桶中陆馁，使用long類型防止相乘時溢出
*
* @param num
* @param n
* @param min
* @param max
* @return
*/
public static int mapToBucket(long num, long n, long min, long max) {
return (int) ((num - min) * n / (max - min));
}
public static int getMaxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) { // 找到數(shù)組的最小值和最大值
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[n + 1]; // 標識桶中是否有數(shù)
int[] bMins = new int[n + 1]; // 桶中最小值
int[] bMaxs = new int[n + 1]; // 桶中最大值
for (int i = 0; i < n; i++) { // 統(tǒng)計每個桶中的最小值和最大值
int b = mapToBucket(nums[i], n, min, max); // 當前元素所在的桶
if (hasNum[b]) {
if (nums[i] < bMins[b]) {
bMins[b] = nums[i];
}
if (nums[i] > bMaxs[b]) {
bMaxs[b] = nums[i];
}
} else {
bMins[b] = bMaxs[b] = nums[i];
hasNum[b] = true;
}
}
int maxGap = 0;
int lastbMax = bMaxs[0]; // 前一個非空桶的最大值找颓，第一個非空桶必是0號桶
int b = 1;
while (b <= n) {
if (hasNum[b]) {
if (bMins[b] - lastbMax > maxGap) { // 當前非空桶的最小值與上一個非空桶的最大值做差，取最大差值
maxGap = bMins[b] - lastbMax;
}
lastbMax = bMaxs[b];
}
b++;
}
return maxGap;
}
public static void main(String[] args) {
int[] arr = new int[]{9, 3, 1, 10};
System.out.println(getMaxGap(arr));
}
}
哦７罚客上的這道相鄰最大差值击狮，可以將代碼提交上去跑跑。
