經(jīng)典數(shù)據(jù)結(jié)構(gòu)題（一）
1、排序問(wèn)題
有一個(gè)整形數(shù)組A，請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法肢簿，算出排序后相鄰兩數(shù)的最大差值。給定一個(gè)int數(shù)組A和A的大小n，請(qǐng)返回最大的差值池充。保證數(shù)組元素個(gè)數(shù)大于等于2小于等于500桩引。
測(cè)試樣例：
[9,3,1,10],4 返回：6
思路：先排序，再遍歷數(shù)組求出相鄰2個(gè)數(shù)的差收夸，保留最大值即可阐污，此時(shí)時(shí)間復(fù)雜度為O(nlogn)。由于非線性時(shí)間比較類(lèi)排序時(shí)間復(fù)雜度不能突破O(nlogn),因此使用桶排序的思想咱圆，對(duì)于n個(gè)數(shù)，設(shè)置n+1個(gè)桶功氨，具體的序苏，先遍歷數(shù)組找出min和max，差值區(qū)間設(shè)置為d=（max-min）/n捷凄，于是區(qū)間是[minmin+d）忱详；[min+dmin+2d）……[min+(n-1)d~min+nd）這n區(qū)間，再單獨(dú)為最大值max設(shè)置一個(gè)桶跺涤，于是得到n+1個(gè)桶匈睁，已知數(shù)組元素總共有n個(gè)，但是桶有n+1個(gè)桶错，并且元素min必定在第一個(gè)桶中航唆，max必定在n+1號(hào)桶中；顯然要把n個(gè)元素放入到n+1個(gè)桶中必定會(huì)產(chǎn)生空桶院刁，已知數(shù)組中的元素時(shí)整數(shù)糯钙，而雖然每個(gè)桶區(qū)間不一定是整數(shù)，例如[23/7退腥，31/7)任岸，但是沒(méi)有關(guān)系，對(duì)于任意一個(gè)元素狡刘，它總會(huì)落入到某一個(gè)桶中享潜，并且可以知道，不同桶之間元素的差值必定大于d,同一個(gè)桶中的元素的差值必定小于d嗅蔬，于是可知要求元素之間的最大差值只需要在不同的桶之間尋找剑按，不用在同一個(gè)桶中尋找，并且題目要求是排序后相鄰2個(gè)元素的最大差值澜术，于是應(yīng)該尋找2個(gè)相鄰非空桶中前一個(gè)桶的最大值與后一個(gè)桶的最小值之間的差值吕座，遍歷所有桶，比較得到所有差值中的最大值就是結(jié)果所要求的相鄰2數(shù)最大差值瘪板。
注意理解：最終要對(duì)每2個(gè)非空的相鄰的桶求差值吴趴，而不能根據(jù)空桶的數(shù)目來(lái)確定2個(gè)相鄰?fù)暗牟钪担驗(yàn)橥暗拈L(zhǎng)度可能是小數(shù)，那么間隔2個(gè)空桶和間隔3個(gè)空桶并不意味著后者具有更大的差值锣枝，因此應(yīng)該對(duì)所有相鄰的非空桶根據(jù)前桶的最大值和后桶的最小值求出差值作為比較對(duì)象厢拭，因此在遍歷時(shí)對(duì)于每一個(gè)桶，要求出這個(gè)桶中元素的最大值maxOfBucket[i]撇叁，最小值minOfBucket[i]供鸠，并且保留上一個(gè)非空桶的maxOfLastBucket，于是差值著2個(gè)相鄰非空桶的差值就是result= minOfBucket[i]- maxOfLastBucket陨闹；然后將當(dāng)前桶的maxOfBucket[i]最為下一個(gè)桶的maxOfLastBucket楞捂。逐步替換result，當(dāng)遍歷完成時(shí)就可以得到最大差值趋厉。
int getBucketID(int num ,int min, int max,int n){
return (int) (num - min) *n /(max - min);
}
int maxGap(int A[],int n){
int maxValue = A[0];
int minValue = A[0];
for (int i = 0; i < n; i++) {
if (maxValue < A[i])maxValue = A[i];
if (minValue > A[i])minValue = A[i];
}
int* mins = (int*)malloc(sizeof(int)*(n + 1));
int* maxs = (int*)malloc(sizeof(int)*(n + 1));
int* hasNum = (int*)malloc(sizeof(int)*(n + 1));
for (int k =0 ; k < n + 1; k++) {
hasNum[k] = 0;
}
int bucketID = 0;
int i = 0;
for (;i < n; i++) {
bucketID = getBucketID(A[i],minValue, maxValue,n);
if (hasNum[bucketID] == 1) {
if (mins[bucketID] > A[i]) {
mins[bucketID] = A[i];
}
if (maxs[bucketID] < A[i]) {
maxs[bucketID] = A[i];
}
}else{
mins[bucketID] = A[i];
maxs[bucketID] = A[i];
}
hasNum[bucketID] = 1;
}
int maxGap = 0;
int lastMax = 0;
i = 0;
while (i < n + 1) {
//找到一個(gè)空桶,記錄下前一個(gè)桶的最大值
while (i < n + 1 && hasNum[i] == 1) {
i++;
}
if (i == n + 1)break;
lastMax = maxs [i-1];
while (i < n + 1 && hasNum[i] == 0) {
i++;
}
if (i == n + 1)break;
if (maxGap <= mins[i] - lastMax) {
maxGap = mins[i] - lastMax;
}
}
free(mins);
free(maxs);
free(hasNum);
return maxGap;
}
2寨闹、最大差值
有一個(gè)長(zhǎng)為n的數(shù)組A，求滿足0≤a≤b<n的A[b]-A[a]的最大值君账。 給定數(shù)組A及它的大小n繁堡，請(qǐng)返回最大差值。
測(cè)試樣例： [10,5],2 返回：0
思路： 從后向前和前邊的最小數(shù)的差值乡数，記錄下來(lái)椭蹄。最后遍歷記錄的數(shù)值找最大的。
int maxDivision(int A[],int n){
int maxValue = 0;
int minValue = A[0];
int temp;
for (int i = 1;i < n;i++) {
if ((temp = A[i] - minValue) > maxValue) {
maxValue = temp;
}
if (minValue > A[i]) {
minValue = A[i];
}
}
return maxValue;
}
