最大系數難題，桶排序面試題

更新時間：2023-01-30 16:11:46 來源：動力節點瀏覽1306次

給定一個數組，求如果排序之后，相鄰兩數的最大差值，要求時間復雜度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;
}

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

但是，比較的基準是非空桶與前后非空桶的比較，而非空桶與前后非空桶的比較

這是為什么呢?

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

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

那么，以空桶為基準可不可以呢?當然不行，這邊呢，有一個我自己手工畫的圖，肯定不好看，但是能看懂。。

桶排序面試題