一道利用桶的算法题

发表于 分类于 阅读次数：

题目

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N),且要求不能用非基于比较的排序

示例

原数组：{4，3，9，6}

排序后数组：{3，4，6，9}
，则相邻两数最大差值为9 - 6 = 3

思路

1.设数组中有N个数,则准备N+1个桶，每个桶对应一个范围（这个范围稍后说明）,桶中存放对应范围内的最大值和最小值，以及一个判断是否为空桶的标记

2.遍历整个数组找到整个数组的min和max分别放入0号桶和N号桶，若max == min 则return 0

3.把min到max的范围等分为N份，而原数组中的值属于哪个范围就放在哪个桶中

我们有N个数和N+1个桶，由此可以推出至少会存在一个空桶，下面来说说空桶的意义。

空桶的意义

空桶的左右两侧迟早会有非空的桶，而这两个非空桶之间的差值必然是大于一个桶的范围的，这样我们就可以排除同一个桶内的差值为最大差值的情况了。
换句话说，最大差值肯定比一个桶的范围大了，那你讨论一个桶内有什么意义呢

回想前面，我们只需要存放对应范围内的最大值和最小值到一个桶中即可，就是因为最大差值必然是在两个相邻的非空桶之间的，我们只需要计算两个相邻的非空桶之间（中间允许有空桶）的最大值和最小值的差，那些情况才有可能是最大差值。

有兄弟萌也许会想直接找空桶两侧的最大差值，但这是不行的，我们只是排除了单个桶内的情况，其他情况我们依旧需要计算。可以看个反例

下面来看下实际代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public static int maxGap(int [] nums) {
        if(nums == null || nums.length < 2) {
            return 0;
        }
        //0 1 2 3
        int len = nums.length;
        //这里并不知道第一个值有多小，所以找个一定比它大的值，这样第一个值就作为min了，max同理
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if(min == max)
            return 0;

        //每个桶都有这三种信息
        boolean[] hasNum = new boolean[len + 1];
        int [] maxs = new int[len + 1];
        int [] mins = new int[len + 1];
        int bid = 0;
        for(int i = 0; i < len; i++) {
            //bid表示当前值要进入哪个桶的下标
            bid = bucket(nums[i] , len, min, max);
            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
            hasNum[bid] = true;
        }

        int res = 0;;
        int lastMax = maxs[0];//前一个最大值
        int i = 1;//前一个是0，所以后一个从1开始
        for(; i <= len; i++) {
            if(hasNum[i]) {
                res = Math.max(res, mins[i] - lastMax);//后一个的最小值 减 前一个的最大值
                lastMax = maxs[i];//等下会i++，所以要先记录前一个的最大值
            }
        }
        return  res;
    }

    //给定一个数num，在min到max的范围内分为len个桶（这样我们才必定有一个空桶），那么num应该在哪个空间
    public static int bucket(long num, long len, long min, long max) {
        return (int) ((num - min) * len / (max - min));
    }