相邻数最大差值

今天群里有人问了一道面试题,题目是N个未排序的整数,在线性时间内,求N个整数在数轴上相邻两个数之间的最大差值。

首先我想吐槽(莫怪~)群里某同学给出的一个解法,用桶排序+线性扫描,按照那位同学的意思,桶排序是O(n),所以整个过程是O(n)。然而并没有什么卵用,这位同学可能不是很了解桶排序的脾气,因为桶排序最乐观情况下才是O(n),而这道题如果使用排序,那结果应该是O(nlogn)。

然后我给出了我的解题思路:

  1. 求 N 个数最大值 MAX,最小值 MIN
  2. 把 [MIN, MAX) 之间平均分成 N 桶,并且补一个桶 [MAX, MAX + AVG),把所有数字放到对应桶里,并且求出每个桶最大值 BMIN 最小值 BMAX
  3. MAX_INTERVAL=MAX(MAX_INTERVAL, 非空桶.BMIN - 前一个非空桶.BMAX)

观点如下:

  1. 如果桶内有多个数,桶内任意数间差值必然小于平均值
  2. 如果两非空桶之间存在空桶,当前非空桶BMIN的值 - 前一个非空桶.BMAX >=平均值
  3. 有N+1个桶,不存在每个桶正好分到一个,必然存在至少一个空桶

最后Talk is cheap, but no comment

func maxDiff(A []int) int {
    N := len(A)
    min := A[0]
    max := A[0]
    for i := 0; i < N; i++ {
        if A[i] > max {
            max = A[i]
        }
        if A[i] < min {
            min = A[i]
        }
    }
    avg := float32(max-min) / float32(N)
    B := make([]struct {
        used bool
        bmax int
        bmin int
    }, N+1)
    for i := 0; i < N; i++ {
        b := &B[int(float32(A[i]-min)/avg)]
        if b.used {
            if A[i] > b.bmax {
                b.bmax = A[i]
            } else if A[i] < b.bmin {
                b.bmin = A[i]
            }
        } else {
            b.bmax = A[i]
            b.bmin = A[i]
            b.used = true
        }
    }
    diff := 0
    lb := 0
    for i := 1; i <= N; i++ {
        if !B[i].used {
            continue
        }
        if B[i].bmin-B[lb].bmax > diff {
            diff = B[i].bmin - B[lb].bmax
        }
        lb = i
    }
    return diff
}

标签: go

已有 2 条评论

  1. 刀之魂 刀之魂

    插值是不是写错了?你的意思是差值吗?

    1. 是的 QAQ, 已改正

添加新评论