推荐练习：如何解决最大间隙算法问题？

本文共计1097个文字，预计阅读时间需要5分钟。

问题描述：最大间隔问题问题描述：给定n个实数x1, x2, ..., xn，求这n个数在实轴上相邻两个数之间的最大差值。假设对于任意实数的下取整时耗时为O(1)，设计最大间隔问题的线性时间算法。

数据输入：

问题描述：
最大间隙问题：给定的n个实数x1,x2...,xn，求这N个数在实轴上相邻两个数之间最大差值。假设对任何实数的下去整耗时是O(1),设计最大间隙问题的线性时间算法。
数据输入：
输入数据由文件名为input.txt的文本文件提供，文件的第一行有一个正整数N，接下来的一行有N个实数x1,x2...,xn
数据输出：
程序运行结束时，将找到的最大间隙输出到output.txt里

这是《算法设计与实验题解》里的一道题，原文中的算法分析是用c写的，我转换成了c#语言，如下
usingSystem;
usingSystem.Diagnostics;
usingSystem.Collections;
usingSystem.IO;
usingSystem.Runtime.InteropServices;

namespaceZuiDaJianXi{
classProgram{
staticintMyFloor(doubled){
cast_structc=newcast_struct{d=d-0.499999999999+6755399441055744.0};
returnc.i;
}

[StructLayout(LayoutKind.Explicit)]
structcast_struct{
[FieldOffset(0)]
publicdoubled;
[FieldOffset(0)]
publicinti;
}
staticunsafeintMyFloor2(doubledval){
dval=dval-0.499999999999;
constdoublemagic=6755399441055744.0;
dval+=magic;
return*(int*)&dval;
}
staticvoidMain(string[]args){
Randomrnd=newRandom();
double[]x=newdouble[10000000];
for(inti=0;i<x.Length;i++)
x[i]=rnd.NextDouble()*100000000;

Stopwatchstop=Stopwatch.StartNew();
//Array.Sort(x);
//x=newdouble[]{1,2,3,4,5};
//Array.ForEach(x,d=>Console.WriteLine("{0}",d));


Console.WriteLine("最大间隙为:{0},time={1}",
maxgap(x.Length,x),stop.ElapsedTicks);
stop.Reset();
stop.Start();
Console.WriteLine("最大间隙为:{0},time={1}",
maxgap2(x),stop.ElapsedTicks);
Console.ReadKey();
}
staticdoublemaxgap2(double[]x){
Array.Sort(x);
doubletmp=0,left=x[0];
for(inti=1;i<x.Length;i++){
doublethisgap=x[i]-left;
left=x[i];
if(thisgap>tmp)tmp=thisgap;
}
returntmp;
}
staticdoublemaxgap(intn,double[]x){
doubleminx=x[mini(n,x)],maxx=x[maxi(n,x)];

//用n-2个等间距的点分割区间[minx,maxx]
//产生n-1个桶，每个桶i中用high[i]和low[i]
//分别存储桶i的数中的最大数和最小数
int[]count=newint[n-1];
double[]low=newdouble[n-1];
double[]high=newdouble[n-1];

//桶初始化
for(inti=0;i<n-1;i++){
count[i]=0;
low[i]=maxx;
high[i]=minx;
}

Stopwatchstop=newStopwatch();
stop.Start();
//将n个数放进n-1个桶中
for(inti=0;i<n;i++){
//底下这句不知道是基于什么数学原理能把一个数
//确定的放入它自己所属的桶里？？
//intbucket=MyFloor(((n-2)*(x[i]-minx)/(maxx-minx)));
intbucket=MyFloor2(((n-2)*(x[i]-minx)/(maxx-minx)));
//intbucket=(int)((n-2)*(x[i]-minx)/(maxx-minx));
count[bucket]++;
if(x[i]<low[bucket])low[bucket]=x[i];
if(x[i]>high[bucket])high[bucket]=x[i];
}
Console.WriteLine("入桶时间：{0}",stop.ElapsedTicks);
//此时除了maxx和minx外的n-2个数放在n-1个桶中
//由鸽舍原理可知，至少有一个桶是空的
//这意味着最大间隙不会出现在同一个桶的两个数之间
//对每个桶做一次线性扫描即可找出最大间隙
doubletmp=0,left=high[0];
for(inti=0;i<n-1;i++){
if(count[i]!=0){
doublethisgap=low[i]-left;
if(thisgap>tmp){
tmp=thisgap;
Console.WriteLine("left={0},thisgap={1}",left,tmp);
}
left=high[i];
}
}

returntmp;
}

staticintmini(intn,double[]x){
doubletemp=x[0];
intk=0;
for(inti=0;i<n;i++){
if(x[i]<temp){
temp=x[i];
k=i;
}
}
returnk;
}
staticintmaxi(intn,double[]x){
doubletemp=x[0];
intk=0;
for(inti=0;i<n;i++){
if(x[i]>temp){
temp=x[i];
k=i;
}
}
returnk;
}
}
}
经测试，在release模式下，输入数据在100w时，maxgap只比maxgap2快1秒，虽然只是快1秒，甚至debug模式下还要比maxgap2还慢，但算法的复杂度比maxgap2要简单很多。后来查了下原因，主要是因为c#的下取整比较耗时，因此造成入桶的时间占总体耗时的百分之八九十，后来在网上找了一些浮点截断成整形的快速算法，发现和c#自带的int强转double的性能差不了多少，汗了，谁要有更好的Floor算法给提供下。

参考链接：
float与double的范围和精度
www.cnblogs.com/tekson/archive/2009/07/16/1524604.html
浮点数到整数的快速转换
www.gamergroup.cn/html/38/n-4338.html
代码优化－之－优化浮点数取整
blog.csdn.net/housisong/archive/2007/05/19/1616026.aspx
其中MyFloor是脑袋提供的，原题出自网上下载的一个《算法设计与实验题解.pdf》文件