給定一個(gè)數(shù)組，求如果排序之后，相鄰兩數(shù)的最大差值，要求時(shí)間復(fù)雜度0(N)

且要求不能用非基于比較的排序

那么這道題就借用了桶排序的概念

#include <stdio.h>
#include <stdbool.h>
int compare_min(int ,int );  //找到最小值 
int compare_max(int ,int );  //找到最大值 
int main ()
{
 int zippo[]={85,41,326,485};
 int n=sizeof(zippo)/sizeof(zippo[0]);
 int w=n+1;
 int min=zippo[0];
 int max=zippo[0];
 for(int i=0;i<n;i++)
 {
  min=compare_min(min,zippo[i]);
  max=compare_max(max,zippo[i]);  
 }
 int group=n+1;              //把組數(shù)設(shè)成整個(gè)數(shù)組中元素的個(gè)數(shù)再+1 
 int bigcha=max-min+1;      //最大值和最小值的差 
 float try_count=bigcha/group;   //想確定每一組中到底要幾個(gè)數(shù)，當(dāng)然了，又可能算出來(lái)的是小數(shù) 
 int count;
 
 
 if(try_count==(int)try_count)  //如果是小數(shù)那么就取整后+1 
  count=try_count;
 else
  count=try_count+1;
 
         //萬(wàn)事俱備，只差三個(gè)數(shù)組  
 bool tong_1 [w]={};        //bool類型的數(shù)組，沒(méi)有初始化之前都是0，用來(lái)判斷是否為空桶 
 int  tong_min [w]={};   //如果不是空桶，那么記下這個(gè)桶的最大值、最小值就好 
 int tong_max [w]={};   //3個(gè)數(shù)組，縱觀為一組，記錄了一個(gè)桶的狀態(tài) 
 for(int i=0;i<n;i++)
 {
  int p=(zippo[i]-min)/count; //這一行求的是：數(shù)組里的數(shù)到底應(yīng)該進(jìn)入哪個(gè)桶 
  if(tong_1[p]==0)
  {
   tong_min[p]=zippo[i];    //只要有一個(gè)數(shù)進(jìn)桶，最大值、最小值都是它 
   tong_max[p]=zippo[i];
   tong_1[p]=1;
  }
  else
  {
   if(zippo[i]<tong_min[p])
    tong_min[p]=zippo[p];
   if(zippo[i]>tong_max[p])
    tong_max[p]=zippo[i];
  }
 }
 int m=0;
 for(int i=1;i<=(n+1);i++)
 {
  if(tong_1[i]==1)
  {
   for(int j=i-1;j>=0;j--)
   {
    if(tong_1[j]==1)
    {
     m=(tong_min[i]-tong_max[j]) > m ? (tong_min[i]-tong_max[j]): m ;
     break;
    }
   }
   for(int k=i+1;k<=(n+1);k++)
   {
    if(tong_1[k]==1)
    {
     m=(tong_min[k]-tong_max[i]) > m ? (tong_min[k]-tong_max[i]) : m ;
     break;
    }
    
   }
  }
 }
 printf("%d",m);
 return 0;
} 
int compare_min(int min,int a)
{
 if(min>a)
  return a;
 else 
  return min;
}
int compare_max(int max,int a)
{
 if(max<a)
  return a;
 else
  return max;
}

所以，桶的信息都記錄好了之后就可以比較了

但是，比較的基準(zhǔn)是非空桶與前后非空桶的比較，而非空桶與前后非空桶的比較

這是為什么呢?

我們把桶數(shù)設(shè)成比數(shù)組的元素個(gè)數(shù)多一的原因，就是要保障至少有一個(gè)空桶，但是這個(gè)空桶的存在只是為了

排除題中所求是一個(gè)桶中的最大值和最小值之差

那么，以空桶為基準(zhǔn)可不可以呢?當(dāng)然不行，這邊呢，有一個(gè)我自己手工畫的圖，肯定不好看，但是能看懂。。

假設(shè)：第一個(gè)桶只在21–30之間有30一個(gè)數(shù)，這種假設(shè)以此類推，那么我們會(huì)發(fā)現(xiàn)第三個(gè)桶和第一個(gè)桶差12，第三個(gè)桶和第四個(gè)桶之間差18

所以呢，由此即可證明，應(yīng)該以非空桶為基準(zhǔn)，以其最大值和后面非空桶的最小值比較，以其最小值和前面非空桶的最大值作比較

以上就是“最大系數(shù)難題，桶排序面試題”，你能回答上來(lái)嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動(dòng)力節(jié)點(diǎn)Java官網(wǎng)。