Java解決計算相鄰兩個數的最大差值的問題
hello，今天給大傢帶來一道算法題。這道算法題，是我目前為止，見過最難的一道題。那麼到底是怎樣的一道算法題呢？如下：
題目：給定一個數組， 求如果排序之後， 相鄰兩數的最大差值。 要求時間復雜度O(N)， 且要求不能用非基於比較的排序。
我查瞭一下，暫時沒有找到一個在線OJ的鏈接，隻能自己寫一個對數器，手動測試瞭。
當初我看到這個題目的時候，說這怎麼可能呢？在一個無序的數組中，求相鄰兩個數據的最大差值。可是我們都知道，現在基於比較的排序算法，最快也隻能夠達到O(N*logN)的水平，而題目明確限制時間復雜度要是O(N)，所以想通過基於比較的排序，排序之後再進行遍歷，時間復雜度肯定是達不到要求的。
有人可能也會想說，不是還有基於非比較的排序算法嗎？比如計數排序、基數排序、桶排序。但是題目又明確規定瞭不能使用基於非比較的排序算法。
這樣的話，想使用排序算法，進行排序，這條路肯定是行不通的。隻能另外想其他的辦法。
——————————————————————————————-我是分割線—————————————————————————————–
重頭戲來瞭！！！整個代碼的流程如下：
1.先遍歷一遍數組，保存整個數組的最大值和最小值。
2.假設數組中一共有N個元素，那麼我們就需要準備N+1個桶。
這每一個桶裡面，可以存儲一定范圍內的數值，而具體可以存儲多大范圍內的數值，需要用公式去計算。比如：第一個桶存儲0……9之間的數，第二個桶存儲10……19的數……
3.我們再次遍歷一遍數組，將每一個數，放入到相應的桶裡。
解釋：為什麼需要進行以上這3個步驟？？？這是一個非常值得思考的問題！！！
由題可知，一共有N個數，但是我們準備瞭N+1個桶。也就是說我們將每個數放入相應的桶中，就算這N個數都在各自的桶裡，無論怎麼放入，始終會多出來1個空桶。
而我們會根據一下這個公式，將每個數放入相應的桶：（arr[i]- min）* N / (max – min)。
以上這個公式，就能夠計算出i位置的數，應該放入哪一個桶裡。根據公式計算，最小值一定會放到第一個桶裡，最大值也一定會放到最後一個桶裡。那麼既然第一個和最後一個桶肯定是有數據的，也就是說明那個空桶肯定是中間的某一個桶。
正是因為這個空桶的存在，會將很多種計算的可能性直接抹殺掉。說的具體點，假設一個桶的存儲數的范圍是0~9，也就是這個桶能夠存儲10個數，既然有一個空桶的話，那麼肯定最後的答案是大於10的。
那麼既然大於10的話，這兩個數肯定不會在同一個桶裡。這樣的話，我們就排除瞭桶裡面兩個數據的情況，隻需要考慮相鄰兩個桶之間的數，才可能是最終的答案。
就如上圖的形式，將所有的數據都放入相應的桶裡。因為有空桶的存在，所以我們的答案必然是在兩個不同桶之間的數據進行相減。而我們在進行相減的時候，隻需要記錄每個桶的最大值和最小值即可。也就是說，用後一個桶的最小值，減前一個桶的最大值。以這樣的形式，循環N次，將每兩個相鄰的桶進行計算，就能得到最終的答案。
既然我們隻需要每個桶裡的最大值和最小值，那就準備兩個數組maxs和mins，分別存儲即可。代碼如下：
以上就是這道題的所有代碼，代碼不多，但是其中的算法思想我覺得真的是很厲害，很難想象出，想到這個方法的是什麼人。
核心就在於那個空桶的存在，抹殺很多的可能性。使其最終的答案隻可能存在於相鄰兩個桶之間的數。
提問：假設給定的某一個數組，算出來桶的數據後，隻有一個是空桶。那麼最終的答案就一定是這個空桶右邊桶的數據減去左邊桶的數據嗎？
最後，我將整個代碼全部放到下面，包括瞭一個對數器，用於測試以上代碼的正確性。
import java.util.Arrays;
public class Code01_CalcTwoNumDiv {
public static void main(String[] args) {
int testTime = 5000; //測試次數
int N = 50; //數組長度
int range = 1000; //數據范圍
boolean flag = true;
for (int i = 0; i < testTime; i++) {
int[] arr = generateArr(N, range);
int p1 = calcTwoNumDiv(arr);
int p2 = sortAfter(arr);
if (p1 != p2) {
flag = false;
break;
}
}
System.out.println(flag? "正確" : "錯誤");
}
public static int calcTwoNumDiv(int[] array) {
if (array == null || array.length < 2) {
return 0;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i : array) { //先遍歷一遍數組，求最大值最小值
max = Math.max(max, i);
min = Math.min(min, i);
}
if (max == min) {
return 0; //如果最大值和最小值相等，說明這個數組隻有這一個數據
}
int len = array.length;
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
//遍歷數據
for (int i = 0; i < array.length; i++) {
int bit = getBit(array[i], len, max, min); //桶的位置
maxs[bit] = hasNum[bit] ? Math.max(maxs[bit], array[i]) : array[i]; //更新最大值
mins[bit] = hasNum[bit] ? Math.min(mins[bit], array[i]) : array[i]; //更新最小值
hasNum[bit] = true; //始終更新為true
}
//第一個桶和最後一個桶，肯定是有數據的。
int preMax = maxs[0];
int res = Integer.MIN_VALUE; //最終的結果
for (int i = 1; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - preMax);
preMax = maxs[i]; //更新前一個的最大值
}
}
return res;
}
public static int getBit(int num, int len, int max, int min) {
return ((num - min) * len) / (max - min); //計算num應該存儲在哪個桶
}
public static int sortAfter(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
Arrays.sort(arr);
int res = Integer.MIN_VALUE;
for (int i = 1; i < arr.length; i++) {
res = Math.max(res, arr[i] - arr[i - 1]);
}
return res;
}
public static int[] generateArr(int N , int range) {
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = (int)(Math.random() * range);
}
return arr;
}
}
到此這篇關於Java解決計算相鄰兩個數的最大差值的問題的文章就介紹到這瞭,更多相關Java 計算相鄰數的最大差值內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！