vlambda博客
学习文章列表

Hard 级别难度?桶排序几行代码搞定!

点击蓝色“五分钟学算法”关注我哟

加个“星标”,一起学算法

今天分享的题目来源于 LeetCode 上第 164 号问题:最大间距。题目难度为 Hard,目前通过率为 50.7% 。

题目描述

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。

说明:

  • 你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。

  • 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

题目解析

题意不难理解,给定一个未排序的数组,找出在排序状态下的相邻元素的最大差值。

如果不仔细看,也许你会觉得这道题简单,它最后说到要求是 O(n) 的时间复杂度,这也就意味着普通排序这条路是走不通的。

这里需要用到的是不经常使用的一种排序方法 —— 桶排序!

首先简单来讲讲桶排序这个算法,这里的桶代表的是一个区间范围,每个桶的区间长度一般都是一样的,比如说给定数组 [1,5,7,10],这里如果我们分 10 个桶,那么每个桶的区间长度就是 1,等同于每个桶其实就对应一个数,如果这里我们分 1 个桶,那么这个桶的区间范围就是 1 ~ 10,当然这里我给的两个例子都是极端的例子,在实际应用上我们应该结合实际情况合理分配桶。

但是基本来说桶的范围和个数是由数组中最大值、最小值以及数组中的元素的个数来决定的,这样可以保证使用最少的桶覆盖所有的可能性。

这个题目要求我们求数组排序好后,相邻数的最大差值,这里我们首先遍历一遍数组得到最大值、最小值,仔细想想的话,如果排序好的数组当中的元素都是等间隔的,类似 [2,4,6,8] ,在数组长度,最大最下值确定的情况下,在这种等间隔的情况下,求得的相邻数的最大差值是最小的,这很好理解,因为同等资源都被等量分配了,不存在分配多和少的结果。

因此,如果我们按这个等量分配的长度来定义桶的长度的话,我们其实并不需要考虑桶内元素的差值,我们需要做的只是记录每个桶中所有元素的最大值和最小值,然后拿这两个值去和相邻的桶的最大值和最小值做差。这样下来可以保证时间复杂度是 O(n) 的。

动画描述

代码实现

  
    
    
  
    
      
      
    
private class Bucket {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
}

public int maximumGap(int[] nums{
    if (nums == null || nums.length < 2) {
        return 0;
    }

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i : nums) {
        min = Math.min(min, i);
        max = Math.max(max, i);
    }

    // 分配桶的长度和个数是桶排序的关键
    // 在 n 个数下,形成的两两相邻区间是 n - 1 个,比如 [2,4,6,8] 这里
    // 有 4 个数,但是只有 3 个区间,[2,4], [4,6], [6,8]
    // 因此,桶长度 = 区间总长度 / 区间总个数 = (max - min) / (nums.length - 1)
    int bucketSize = Math.max(1, (max - min) / (nums.length - 1));

    // 上面得到了桶的长度,我们就可以以此来确定桶的个数
    // 桶个数 = 区间长度 / 桶长度
    // 这里考虑到实现的方便,多加了一个桶,为什么?
    // 还是举上面的例子,[2,4,6,8], 桶的长度 = (8 - 2) / (4 - 1) = 2
    //                           桶的个数 = (8 - 2) / 2 = 3
    // 已知一个元素,需要定位到桶的时候,一般是 (当前元素 - 最小值) / 桶长度
    // 这里其实利用了整数除不尽向下取整的性质
    // 但是上面的例子,如果当前元素是 8 的话 (8 - 2) / 2 = 3,对应到 3 号桶
    //              如果当前元素是 2 的话 (2 - 2) / 2 = 0,对应到 0 号桶
    // 你会发现我们有 0,1,2,3 号桶,实际用到的桶是 4 个,而不是 3 个
    // 透过例子应该很好理解,但是如果要说根本原因,其实是开闭区间的问题
    // 这里其实 0,1,2 号桶对应的区间是 [2,4),[4,6),[6,8)
    // 那 8 怎么办?多加一个桶呗,3 号桶对应区间 [8,10)
    Bucket[] buckets = new Bucket[(max - min) / bucketSize + 1];

    for (int i = 0; i < nums.length; ++i) {
        int loc = (nums[i] - min) / bucketSize;

        if (buckets[loc] == null) {
            buckets[loc] = new Bucket();
        }

        buckets[loc].min = Math.min(buckets[loc].min, nums[i]);
        buckets[loc].max = Math.max(buckets[loc].max, nums[i]);
    }

    int previousMax = Integer.MAX_VALUE; int maxGap = Integer.MIN_VALUE;
    for (int i = 0; i < buckets.length; ++i) {
        if (buckets[i] != null && previousMax != Integer.MAX_VALUE) {
            maxGap = Math.max(maxGap, buckets[i].min - previousMax);
        }

        if (buckets[i] != null) {
            previousMax = buckets[i].max;
            maxGap = Math.max(maxGap, buckets[i].max - buckets[i].min);
        }
    }

    return maxGap;
}




本文相关阅读推荐: