[ 算法 ] 一维数据的最大间隙

问题

最大间隙问题：给定 n 个实数x1，x2，...，xn，求这 n 个数在实轴上相邻 2 个数之间的最大差值。假设对任何实数的下取整函数耗时 O(1)，设计解最大间隙问题的线性时间算法。

时间复杂度：O(n)

算法基于桶排序
鸽舍原理（在同一个区间内不会存在最大差值）
对桶排序进行改良(只记录桶内的最大最小值)

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define mmax 1000 //该值随意
#define mmin 0    //该值随意

int main()
{
    //参数变量
    int n, i, bucket;
    double maxValue = mmin, minValue = mmax, begin, maxgap = 0.0, temp;

    //数组个数
    scanf("%d", &n);

    double* num = new double[n];//存放数据的数组

    //定义Bucket
    int* count = new int[n]; //计数
    double* maxNum = new double[n];//桶内的最大值
    double* minNum = new double[n];//桶内的最小值

    //找出最大值最小值
    for (i = 0; i < n; i++) {
        scanf("%lf", &num[i]);

        if (num[i] > maxValue)
            maxValue = num[i];

        if (num[i] < minValue)
            minValue = num[i];
    }

    //初始化桶
    for (int i = 0; i < n; i++) {
        count[i] = 0;
        maxNum[i] = minValue;
        minNum[i] = maxValue;
    }

    //桶排序
    for (i = 0; i < n; i++) {
        //计算该值所在的区间(桶)
        bucket = (int)((num[i] - minValue) / ((maxValue - minValue) / (n - 1)));
        count[bucket]++;//当前桶计数+1
        if (maxNum[bucket] < num[i])//当前桶内的最大值
            maxNum[bucket] = num[i];
        if (minNum[bucket] > num[i])//当前桶内的最小值
            minNum[bucket] = num[i];

    }

    //前提：鸽舍原理可知 最大差值不会出现在同一个区间内(桶)

    //初始值比较值
    begin = maxNum[0];

    //开始便利查找桶之间的最大差值
    for (i = 1; i < n; i++) {
        if (count[i]) {//桶中的元素不为空则查找

            //计算相邻两个桶"区间边"上的差值(即第i个区间的最大值和第i+1区间的最小值的差值)
            //因为第i个区间(桶)的最大值一定比第i+1个区间的最小值还小
            temp = minNum[i] - begin;
            if (temp > maxgap)//不断遍历所有桶查找比较找出最差大值的值
                maxgap = temp;
            begin = maxNum[i];//当查找到最大差值时将当前桶中最大值最为下一次比较的初始值；
        }
    }
    printf("%.2f\n", maxgap);
    return 0;
}