Java解決計(jì)算相鄰兩個(gè)數(shù)的最大差值的問題

第Java解決計(jì)算相鄰兩個(gè)數(shù)的最大差值的問題hello，今天給大家?guī)硪坏浪惴}。這道算法題，是我目前為止，見過最難的一道題。那么到底是怎樣的一道算法題呢？如下：

題目：給定一個(gè)數(shù)組，求如果排序之后，相鄰兩數(shù)的最大差值。要求時(shí)間復(fù)雜度O(N)，且要求不能用非基于比較的排序。

我查了一下，暫時(shí)沒有找到一個(gè)在線OJ的鏈接，只能自己寫一個(gè)對(duì)數(shù)器，手動(dòng)測(cè)試了。

當(dāng)初我看到這個(gè)題目的時(shí)候，說這怎么可能呢？在一個(gè)無序的數(shù)組中，求相鄰兩個(gè)數(shù)據(jù)的最大差值。可是我們都知道，現(xiàn)在基于比較的排序算法，最快也只能夠達(dá)到O(N*logN)的水平，而題目明確限制時(shí)間復(fù)雜度要是O(N)，所以想通過基于比較的排序，排序之后再進(jìn)行遍歷，時(shí)間復(fù)雜度肯定是達(dá)不到要求的。

有人可能也會(huì)想說，不是還有基于非比較的排序算法嗎？比如計(jì)數(shù)排序、基數(shù)排序、桶排序。但是題目又明確規(guī)定了不能使用基于非比較的排序算法。

這樣的話，想使用排序算法，進(jìn)行排序，這條路肯定是行不通的。只能另外想其他的辦法。

-------------------------------------------------------------------------------------------我是分割線-----------------------------------------------------------------------------------------

重頭戲來了?。?！整個(gè)代碼的流程如下：

1.先遍歷一遍數(shù)組，保存整個(gè)數(shù)組的最大值和最小值。

2.假設(shè)數(shù)組中一共有N個(gè)元素，那么我們就需要準(zhǔn)備N+1個(gè)桶。

這每一個(gè)桶里面，可以存儲(chǔ)一定范圍內(nèi)的數(shù)值，而具體可以存儲(chǔ)多大范圍內(nèi)的數(shù)值，需要用公式去計(jì)算。比如：第一個(gè)桶存儲(chǔ)0……9之間的數(shù)，第二個(gè)桶存儲(chǔ)10……19的數(shù)……

3.我們?cè)俅伪闅v一遍數(shù)組，將每一個(gè)數(shù)，放入到相應(yīng)的桶里。

解釋：為什么需要進(jìn)行以上這3個(gè)步驟？？？這是一個(gè)非常值得思考的問題?。。?/p>

由題可知，一共有N個(gè)數(shù)，但是我們準(zhǔn)備了N+1個(gè)桶。也就是說我們將每個(gè)數(shù)放入相應(yīng)的桶中，就算這N個(gè)數(shù)都在各自的桶里，無論怎么放入，始終會(huì)多出來1個(gè)空桶。

而我們會(huì)根據(jù)一下這個(gè)公式，將每個(gè)數(shù)放入相應(yīng)的桶：（arr[i]-min）*N/(max-min)。

以上這個(gè)公式，就能夠計(jì)算出i位置的數(shù)，應(yīng)該放入哪一個(gè)桶里。根據(jù)公式計(jì)算，最小值一定會(huì)放到第一個(gè)桶里，最大值也一定會(huì)放到最后一個(gè)桶里。那么既然第一個(gè)和最后一個(gè)桶肯定是有數(shù)據(jù)的，也就是說明那個(gè)空桶肯定是中間的某一個(gè)桶。

正是因?yàn)檫@個(gè)空桶的存在，會(huì)將很多種計(jì)算的可能性直接抹殺掉。說的具體點(diǎn)，假設(shè)一個(gè)桶的存儲(chǔ)數(shù)的范圍是0~9，也就是這個(gè)桶能夠存儲(chǔ)10個(gè)數(shù)，既然有一個(gè)空桶的話，那么肯定最后的答案是大于10的。

那么既然大于10的話，這兩個(gè)數(shù)肯定不會(huì)在同一個(gè)桶里。這樣的話，我們就排除了桶里面兩個(gè)數(shù)據(jù)的情況，只需要考慮相鄰兩個(gè)桶之間的數(shù)，才可能是最終的答案。

就如上圖的形式，將所有的數(shù)據(jù)都放入相應(yīng)的桶里。因?yàn)橛锌胀暗拇嬖?，所以我們的答案必然是在兩個(gè)不同桶之間的數(shù)據(jù)進(jìn)行相減。而我們?cè)谶M(jìn)行相減的時(shí)候，只需要記錄每個(gè)桶的最大值和最小值即可。也就是說，用后一個(gè)桶的最小值，減前一個(gè)桶的最大值。以這樣的形式，循環(huán)N次，將每?jī)蓚€(gè)相鄰的桶進(jìn)行計(jì)算，就能得到最終的答案。

既然我們只需要每個(gè)桶里的最大值和最小值，那就準(zhǔn)備兩個(gè)數(shù)組maxs和mins，分別存儲(chǔ)即可。代碼如下：

以上就是這道題的所有代碼，代碼不多，但是其中的算法思想我覺得真的是很厲害，很難想象出，想到這個(gè)方法的是什么人。

核心就在于那個(gè)空桶的存在，抹殺很多的可能性。使其最終的答案只可能存在于相鄰兩個(gè)桶之間的數(shù)。

提問：假設(shè)給定的某一個(gè)數(shù)組，算出來桶的數(shù)據(jù)后，只有一個(gè)是空桶。那么最終的答案就一定是這個(gè)空桶右邊桶的數(shù)據(jù)減去左邊桶的數(shù)據(jù)嗎？

最后，我將整個(gè)代碼全部放到下面，包括了一個(gè)對(duì)數(shù)器，用于測(cè)試以上代碼的正確性。

importjava.util.Arrays;

publicclassCode01_CalcTwoNumDiv{

publicstaticvoidmain(String[]args){

inttestTime=5000;//測(cè)試次數(shù)

intN=50;//數(shù)組長(zhǎng)度

intrange=1000;//數(shù)據(jù)范圍

booleanflag=true;

for(inti=0;itestTime;i++){

int[]arr=generateArr(N,range);

intp1=calcTwoNumDiv(arr);

intp2=sortAfter(arr);

if(p1!=p2){

flag=false;

break;

System.out.println(flag"正確":"錯(cuò)誤");

publicstaticintcalcTwoNumDiv(int[]array){

if(array==null||array.length2){

return0;

intmax=Integer.MIN_VALUE;

intmin=Integer.MAX_VALUE;

for(inti:array){//先遍歷一遍數(shù)組，求最大值最小值

max=Math.max(max,i);

min=Math.min(min,i);

if(max==min){

return0;//如果最大值和最小值相等，說明這個(gè)數(shù)組只有這一個(gè)數(shù)據(jù)

intlen=array.length;

boolean[]hasNum=newboolean[len+1];

int[]maxs=newint[len+1];

int[]mins=newint[len+1];

//遍歷數(shù)據(jù)

for(inti=0;iarray.length;i++){

intbit=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

//第一個(gè)桶和最后一個(gè)桶，肯定是有數(shù)據(jù)的。

intpreMax=maxs[0];

intres=Integer.MIN_VALUE;//最終的結(jié)果

for(inti=1;i=len;i++){

if(hasNum[i]){

res=Math.max(res,mins[i]-preMax);

preMax=maxs[i];//更新前一個(gè)的最大值

returnres;

publicstaticintgetBit(intnum,intlen,intmax,intmin){

return((num-min)*len)/(max-min);//計(jì)算num應(yīng)該存儲(chǔ)在哪個(gè)桶

publicstaticintsortAfter(int[]arr){

if(arr==null||arr.length2){

return0;

Arrays.sort(arr);

intres=Integer.MIN_VALUE;

for(inti=1;iarr.length;i++){

res=Math.max(res,arr[i]-arr[i-1