Blog

leetcode164最大间距

leetcode 164 Maximum Gap

Posted by BY on July 20, 2020

前言

持续更新了

正文

问题来源

本问题来自leetcode上的164题。

问题描述

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。

示例 1:

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

示例 2:

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

分析：

基数排序，然后取当前数字减前一位的最大值

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func bucketSort(nums []int) {
    aux := make([]int, len(nums))
    tmax := math.MinInt32
    for _, v := range nums {
        tmax = max(tmax, v)
    }
    evap := 1
    base := 10
    for tmax != 0 {
        count := make([]int, base)
        for i := 0; i < len(nums); i++ {
            count[nums[i]/evap%base]++
        }
        for i := 1; i < base; i++ {
            count[i] += count[i-1]
        }
        for i := len(nums)-1; i >= 0; i-- { // 一定是逆序处理
            count[nums[i]/evap%base]--
            aux[count[nums[i]/evap%base]] = nums[i]
        }
        copy(nums, aux)
        tmax /= base
        evap *= base
    }
}

func maximumGap(nums []int) int {
    bucketSort(nums)
    tmax := 0
    for i := 1; i < len(nums); i++ {
        tmax = max(tmax, nums[i]-nums[i-1])
    }
    return tmax
}

桶和鸽笼原理
鸽笼原理描述说，n 个物品放入 m 个容器中，如果 n > m 那么一定有一个容器装有至少两个物品。
假设对于数组中的任意一个元素都有一个桶，那么每个元素恰好占据一个桶。现在减少桶的个数，必然会有一些桶包含超过一个元素。
现在讨论元素之间的间距。考虑最好情况，假设元素排好序且两两之间间距相同。这意味着任意相邻元素都有恒定的差值。所以 nn 个元素有 n-1n−1 个间距，假设为 tt，显然可以得到 t = (max - min)/(n-1)t=(max−min)/(n−1)，其中 maxmax 和 minmin 是数组中最大和最小的元素。这个间距就是相邻元素间最大间距，也就是我们要的答案。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a 
    }
    return b
}

type Bucket struct {
    used bool
    min int
    max int
}

func NewBucket() Bucket {
    return Bucket{false, math.MaxInt32, math.MinInt32}
}

func maximumGap(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }
    tmax := math.MinInt32
    tmin := math.MaxInt32
    for i := 0; i < len(nums); i++ {
        tmin = min(tmin, nums[i])
        tmax = max(tmax, nums[i])
    }
    size := max(1,(tmax-tmin)/(len(nums)-1))
    n := (tmax-tmin)/size + 1
    buckets := make([]Bucket, n)
    // init
    for i := 0; i < n; i++ {
        buckets[i] = NewBucket()
    }
    for i := 0; i < len(nums); i++ {
        index := (nums[i]-tmin)/size
        buckets[index].used = true
        buckets[index].min = min(buckets[index].min, nums[i])
        buckets[index].max = max(buckets[index].max, nums[i])
    }
    preMax := tmin
    res := 0
    for i := 0; i < n; i++ {
        if buckets[i].used {
            res = max(res, buckets[i].min - preMax)
            preMax = buckets[i].max
        }
    }
    return res
}

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog