最大间隙问题

问题提出

    给定 n 个实数，求这n个实数在数轴上相邻2个数之间的最大差值，设计解最大间隙问题的线性时间算法。

问题分析

   最简单的方法便是先将实数进行排序，然后计算间隙，并求出最大间隙。但是这不满足线性时间算法要求。而鸽笼原理，可以解决此类问题。首先，要找出最大值和最小值，并均匀分成n-1个区间，计算实数分布到了哪个区间中，用区间的最小值减去前一个区间的最大值，这便是所求间隙，经过比较，即可求的最大间隙。

    

    

#include<stdio.h>
#include<math.h>

#define N 5

int main(){
	float maxvalue,minvalue;
	float intmax[N-1],intmin[N-1];
	float a[N]={2.3,3.1,7.5,1.5,6.3};
	int count[N];
	int index;
	float left,gap,len,maxgap=0.0;
	 
	maxvalue=0;
	minvalue=9999.;
	for(int j=0;j<N;j++){
		if(maxvalue<a[j])
			maxvalue=a[j];
		if(minvalue>a[j])
			minvalue=a[j];
	}
 	 
	for(int i=0;i<N-1;i++){
		intmax[i]=minvalue;
		intmin[i]=maxvalue;
		count[i]=0;
	}
	gap=(float)((maxvalue-minvalue)/(N-1));
	for(int i=0;i<N;i++){
		index=(int)((a[i]-minvalue)/gap);
		count[index]++;
		if(intmax[index]<a[i]){
			intmax[index]=a[i];
		}
		if(intmin[index]>a[i]){
			intmin[index]=a[i];
		}
	}
 	left=intmax[0];
	for(int i=0;i<N-1;i++){
		if(count[i+1]){
			len=intmin[i+1]-left;
			if(len>maxgap){
				maxgap=len;
			}
			left=intmax[i+1];
		}
	 
	}
	printf("%3.2f\n",maxgap); 
}