最大系数难题，桶排序面试题

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度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;              //把组数设成整个数组中元素的个数再+1 
 int bigcha=max-min+1;      //最大值和最小值的差 
 float try_count=bigcha/group;   //想确定每一组中到底要几个数，当然了，又可能算出来的是小数 
 int count;
 
 
 if(try_count==(int)try_count)  //如果是小数那么就取整后+1 
  count=try_count;
 else
  count=try_count+1;
 
         //万事俱备，只差三个数组  
 bool tong_1 [w]={};        //bool类型的数组，没有初始化之前都是0，用来判断是否为空桶 
 int  tong_min [w]={};   //如果不是空桶，那么记下这个桶的最大值、最小值就好 
 int tong_max [w]={};   //3个数组，纵观为一组，记录了一个桶的状态 
 for(int i=0;i<n;i++)
 {
  int p=(zippo[i]-min)/count; //这一行求的是：数组里的数到底应该进入哪个桶 
  if(tong_1[p]==0)
  {
   tong_min[p]=zippo[i];    //只要有一个数进桶，最大值、最小值都是它 
   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;
}

所以，桶的信息都记录好了之后就可以比较了

但是，比较的基准是非空桶与前后非空桶的比较，而非空桶与前后非空桶的比较

这是为什么呢?

我们把桶数设成比数组的元素个数多一的原因，就是要保障至少有一个空桶，但是这个空桶的存在只是为了

排除题中所求是一个桶中的最大值和最小值之差

那么，以空桶为基准可不可以呢?当然不行，这边呢，有一个我自己手工画的图，肯定不好看，但是能看懂。。

假设：第一个桶只在21–30之间有30一个数，这种假设以此类推，那么我们会发现第三个桶和第一个桶差12，第三个桶和第四个桶之间差18

所以呢，由此即可证明，应该以非空桶为基准，以其最大值和后面非空桶的最小值比较，以其最小值和前面非空桶的最大值作比较

以上就是“最大系数难题，桶排序面试题”，你能回答上来吗?如果想要了解更多的相关内容，可以关注极悦Java官网。