大数据量的处理

15. 最大间隙问题 给定n个实数 ，求着n个实数在实轴上向量2个数之间的最大差值，要求线性的时间算法。 方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法： s 找到n个数据中最大和最小数据max和min。 s 用n-2个点等分区间[min, max]，即将[min, max]等分为n-1个区间（前闭后开区间），将这些区间看作桶，编号为 ，且桶 的上界和桶i+1的下届相同，即每个桶的大小相同。每个桶的大小为： 。实际上，这些桶的边界构成了一个等差数列（首项为min，公差为 ），且认为将min放入第一个桶，将max放入第n-1个桶。 s 将n个数放入n-1个桶中：将每个元素 分配到某个桶（编号为index），其中 ，并求出分到每个桶的最大最小数据。 s 最大间隙：除最大最小数据max和min以外的n-2个数据放入n-1个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙 不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶（即便好在该连个便好之间的桶）一定是空桶。也就是说，最大间隙在桶 i的上界和桶j的下界之间产生 。一遍扫描即可完成。 --------------------- 本文来自 Aldeo 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/zhangzijiejiayou/article/details/50616520?utm_source=copy