題目：

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

解法：

首先，輸入的數(shù)組是還沒(méi)有排好序的，題目要求是不能使用非基于比較的排序而且排序算法的時(shí)間復(fù)雜度最低都要O(NlogN)，這不符合題目要求的時(shí)間復(fù)雜度O(N)，所以我們不能用普通的排序算法去解決該問(wèn)題。要做到時(shí)間復(fù)雜度為O(N)，那么第一時(shí)間想到的就是遍歷數(shù)組的時(shí)候只會(huì)對(duì)數(shù)組遍歷一趟。

這里給大家介紹一種非常巧妙的算法解決該問(wèn)題。

假如數(shù)組中有n個(gè)數(shù)，遍歷一遍數(shù)組得到數(shù)組中的最大值my_max，最小值my_min，然后我們?yōu)檫@n個(gè)數(shù)準(zhǔn)備n+1個(gè)桶來(lái)裝這n個(gè)數(shù)。

如我們的輸入數(shù)組中有9個(gè)數(shù)，遍歷一遍數(shù)組后得到數(shù)組中的最小值my_min和最大值my_max.

若my_min等于my_max，則說(shuō)明數(shù)組中的這9個(gè)數(shù)都是一樣的，那立馬返回相鄰兩數(shù)的最大差值為0.

若my_min不等于my_max，此刻假設(shè)my_min=0，my_max=99，然后因?yàn)閿?shù)組有9個(gè)數(shù)，那桶的數(shù)目就為10個(gè)，my_min是第一個(gè)桶的最小值，my_max是最后一個(gè)桶的最大值.

然后再?gòu)念^開(kāi)始遍歷數(shù)組，數(shù)組中的最小值一定進(jìn)入0號(hào)桶，數(shù)組中的最大值一定進(jìn)入9號(hào)桶，數(shù)組中的其他元素也依次進(jìn)桶.

現(xiàn)在有一個(gè)很重要的結(jié)論，那就是，9個(gè)數(shù)，10個(gè)桶，遍歷完一輪數(shù)組之后，其中第一個(gè)桶和最后一個(gè)桶一定不為空，而且，中間的桶必定至少有一個(gè)桶是空桶！

還是用上述提到的例子，假設(shè)每一個(gè)桶內(nèi)的元素都是按從小到大排好序的，而且0~9號(hào)桶也是按從小到大排好序(1號(hào)桶里的元素比0號(hào)桶里的元素都大，2號(hào)桶里的元素比1號(hào)桶里的元素都大)，所以整個(gè)數(shù)組就可看成是排好序的。因?yàn)榭胀暗拇嬖?#xff0c;相鄰兩數(shù)的最大差值有如下的情況。

1.桶內(nèi)相鄰兩數(shù)的最大差值

可以看出，一個(gè)桶內(nèi)的相鄰最大差值最大也就可能是9-0=9.

2.桶間相鄰兩數(shù)的最大差值(中間無(wú)空桶)

可以看出，桶間相鄰兩數(shù)的最大差值(中間無(wú)空桶)的最大差值的范圍是1~19.

3.桶間相鄰兩數(shù)的最大差值(中間有空桶)

可以看出，桶間相鄰兩數(shù)的最大差值(中間有空桶)的最大差值的范圍是10~29.正是中間有空桶的存在，就完美排除掉了第1種情況(桶內(nèi)相鄰兩數(shù)的最大差值)，也即，排好序的數(shù)組中的兩數(shù)最大差值，那兩個(gè)數(shù)絕對(duì)不可能在一個(gè)桶內(nèi)！

所以，排序后數(shù)組的相鄰兩數(shù)最大差值出現(xiàn)的情況只可能是上面的情況2和情況3，因此只需要判斷相鄰兩個(gè)桶的相鄰兩數(shù)的最大即可，也即把所有桶都遍歷一遍，然后用該桶的最小值減去前一個(gè)非空桶的最大值(因?yàn)檫@樣才是數(shù)組排序后的相鄰兩個(gè)數(shù))，然后最后得出最大差值。

下面舉一個(gè)例子來(lái)說(shuō)明整個(gè)算法的流程。

輸入一個(gè)數(shù)組[17, 0, 99, 23, 67, 13, 14, 89, 4]，因?yàn)檫@個(gè)數(shù)組有9個(gè)數(shù)，所以分配10個(gè)桶。

先遍歷整個(gè)數(shù)組，找出最小值my_min=0，最大值my_max=99.

分配10個(gè)桶，編號(hào)為0~9.

3.遍歷數(shù)組，依次入桶，記錄每個(gè)桶的最小值和最大值.入桶的算法為

，num為當(dāng)前值，Len為數(shù)組長(zhǎng)度，得到的結(jié)果為該num應(yīng)該入幾號(hào)桶。

代碼：

class MaxGap {public：int maxGap(vector<int> nums){if (nums.size()<2)return 0;int len=nums.size();int my_min=INT_MIN;int my_max=INT_MAX;//找出最小值和最大值for (int i=0;i<len;i++){my_min=min(my_min,nums[i]);my_max=max(my_max,nums[i]);}if (my_min==my_max){return 0;}bool *hasNum=new bool[len+1];int *mins=new int[len+1];int *maxs=new int[len+1];int bid=0;for (int i=0;i<len;i++){//當(dāng)前這個(gè)數(shù)應(yīng)該去幾號(hào)桶bid=bucket(nums[i],len,my_min,my_max);//更新這個(gè)桶的最小值mins[bid]=hasNum[bid]?min(mins[bid],nums[i]):nums[i];//更新這個(gè)桶的最大值maxs[bid]=hasNum[bid]?max(maxs[bid],nums[i]):nums[i];hasNum[bid]=true;}//找到每個(gè)非空與前一個(gè)非空桶的最大差值int res=0;int lastMax=maxs[0];int i=1;for (;i<=len;i++){if (hasNum[i]){//相鄰兩個(gè)桶之間的最大差值比較，大的賦值給resres=max(res,mins[i]-lastMax);lastMax=maxs[i];}}return res;}//當(dāng)前這個(gè)數(shù)應(yīng)該去幾號(hào)桶int bucket(long num,long len,long my_min,long my_max){return (int) ((num-my_min)*len/(my_max-my_min));} }

總結(jié)

以上是生活随笔為你收集整理的如何得出数组里最大_相邻两数的最大差值（超巧妙解法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。