问题描述：
最大间隙问题：给定n 个实数x1 , x2 , , xn ，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。
编程任务：
对于给定的n 个实数 x1 , x2, ……, xn，编程计算它们的最大间隙。
数据样例：
输入数据：
5
2.3 3.1 7.5 1.5 6.3
输出数据：
3.2
算法思想分析：
对于给定的n 个实数先取得其最大值和最小值，n个数的大小范围为[min,max];剩余n-2个点等分区间[min,max]产生n-1个闭区间的桶,如果我们假设每个桶的区间为[,)所以要增加一个桶放max共n个桶。max放入最后一个桶中，所以除max外的n-1个数置于n-1个桶中，由于min固定被放入第一桶里，剩下的n-2个数据，如果还存在数据放入第一桶则势必存在至少有一个桶为空，则意味着最大间隙不会出现在同一个桶中的两个数之间。如果剩下的数据不放人第一桶，则n-2数据放入n-2个桶中，如果同一个桶中有两个数，则必然出现有一个桶为空。所以最大间隙不会出现在同一个桶中，所以只需要记录桶中的最大值和最小值。所以最大值为对每个桶做一次线性扫描，比较 过滤掉空桶的所有桶中相邻两桶取(后面桶的最小值 - 前面桶的最大值)的最大值。
//求数组中最小数据下标和最大数据下标 static void GetIndex(double[] array,out int indexMin,out int indexMax) { indexMin = 0; indexMax = 0; double tempMin = array[0]; double tempMax = array[0]; for (int i = 1; i < array.Length; i++) { if (array[i] < tempMin) { tempMin = array[i]; indexMin = i; } if (array[i] > tempMax) { tempMax = array[i]; indexMax = i; } } }
定义数据结构
View Code public struct Gap { //实际分配到该桶的数据个数 public int Count { get; set; } //记录分配到该桶的最小数据 public double Low { get; set; } //记录分配到该桶的最大数据 public double High { get; set; } }
获取最大间隙值
static double GetMaxGap(double[] array) { int indexMin; int indexMax; GetIndex(array, out indexMin, out indexMax); double min = array[indexMin]; double max = array[indexMax]; //用length-2个点等分区间[min,max]产生length-1个桶,每个桶的区间为[,)所以要增加一个最后一个桶放max Gap[] gaps = new Gap[array.Length]; //构造桶时,Low赋最大值,High赋最小值 for (int i = 0; i < gaps.Length; i++) { gaps[i].Count = 0; gaps[i].Low = max; gaps[i].High = min; } //由于min放入第一个桶，max放入最后一个桶中，所以除max外的length-1个数置于length-1个桶中， //由于min固定被放入第一桶里，剩下的length-2个数据，如果还存在数据放入第一桶则势必存在至少有一个桶为空，则意味着最大间隙不会出现在同一个桶中的两个数之间 //如果剩下的数据不放人第一桶，则length-2数据放入length-2个桶中，如果同一个桶中有两个数，则必然出现有一个桶为空 //所以最大间隙不会出现在同一个桶中，所以只需要记录桶中的最大值和最小值 //初始化桶中最小值、最大值 for (int i = 0; i < array.Length; i++) { int bucket = (int)((array.Length - 1)*(array[i] - min) / (max - min)); gaps[bucket].Count++; if (array[i] < gaps[bucket].Low) gaps[bucket].Low = array[i]; //记录桶里的最小值 if (array[i] > gaps[bucket].High) gaps[bucket].High = array[i]; //记录桶里的最大值 } double maxGap = 0; double left = gaps[0].High; //初始值为第一个桶中的最大值 如果第一个桶为空则为min值 //对每个桶做一次线性扫描，比较 过滤掉空桶的所有桶中相邻两桶取(后面桶的最小值 - 前面桶的最大值)的最大值 for (int i = 0; i < gaps.Length; i++) { //如果桶中有值 if (gaps[i].Count != 0) { double tempGap = gaps[i].Low - left; if (tempGap > maxGap) maxGap = tempGap; left = gaps[i].High; } } return maxGap; }
总结：以上纯属个人的理解，对于有些地方觉得还是理解不是很深，有不足之处和错误的地方希望大家帮我指出。谢谢