最大间隔问题

给定  n 个实数 ，找出这n个数在实轴上相邻两个数 的 最大差值

如输入  2.3, 3.1, 7.5, 1.5, 6.3  (注意 无序哦)

最大差值：6.3-3.1=3.2

赫赫 ，不要先想排序 ! 

提示：

利用 鸽笼原理  ：5个数，设 6个相同大小的桶在实轴上覆盖5个数 ， 则必有一桶里没有数字 ，则知道最大差值了吧 ，嘿嘿，线性算法！

代码：

 

/**
 * Author: yiminghe
 * Date: 2008-10-7
 * Time: 23:14:27
 * Any problem ,contact [email protected]
 */
public class GapSearch {

    //类内 函数内 变量初始化 

    private static double getMin(double[] data) {
        if (data.length < 1)
            throw new IllegalArgumentException("argument error");
        double min = data[0];
        for (int i = 1; i < data.length; i++) {
            min = Math.min(min, data[i]);
        }
        return min;

    }

    private static double getMax(double[] data) {
        if (data.length < 1)
            throw new IllegalArgumentException("argument error");
        double max = data[0];
        for (int i = 1; i < data.length; i++) {
            max = Math.max(max, data[i]);
        }
        return max;

    }

    private static double gap(double[] data) {

        double min = getMin(data);
        double max = getMax(data);
        if (data.length == 2)
            return max - min;
        int bucket = data.length + 1;
        int[] count = new int[bucket];
        double[] low = new double[bucket];
        double[] high = new double[bucket];
        for (int i = 0; i < bucket; i++) {
            low[i] = max;
            high[i] = min;
        }

        double gapV = (max - min) / bucket;

        for (int i = 0; i < data.length; i++) {
            int gapC = (int) ((data[i] - min) / gapV);
            gapC = (gapC == bucket) ? gapC - 1 : gapC;
            count[gapC]++;
            low[gapC] = Math.min(low[gapC], data[i]);
            high[gapC] = Math.max(high[gapC], data[i]);
        }

        double left = high[0];
        double maxGap = 0;
        for (int i = 1; i < bucket; i++) {
            if (count[i] != 0) {
                System.out.println(low[i] + "  -  " + high[i]);
                maxGap = Math.max(maxGap, low[i] - left);
                left = high[i];
            }
        }

        return maxGap;

    }


    public static void main(String[] args) {

        double[] data = new double[]{2.3d, 3.1d, 7.5d, 1.5d, 6.3d};

        System.out.println(gap(data));
    }
}