【Python】给定整数数组A[0…N-1]，求这N个数排序后最大间隔

最大间隔

给定整数数组A[0…N-1]，求这N个数排序后最大间隔。如：1,7,14,9,4,13的最大间隔为4。
排序后：1,4,7,9,13,14，最大间隔是13-9=4
显然，对原数组排序，然后求后项减前项的最大值，即为解。
可否有更好的方法？

问题分析

假定N个数的最大最小值为max，min，则这N个数形成N-1个间隔
如果N个数完全均匀分布，则间距全部是(max-min)/(N-1)且最小；
如果N个数不是均匀分布，间距不均衡，则最大间距必然大于(max-min)/(N-1)

解决思路

思路：将N个数用间距 分成N-1个区间，则落在同一区间内的数不可能有最大间距。统计后一区间的最小值与前一区间的最大值的差即可。
若没有任何数落在某区间，则该区间无效，不参与统计。
显然，这是借鉴桶排序/Hash映射的思想

桶的数目

同时，N-1个桶是理论值，会造成若干个桶的数目比其他桶大1，从而造成统计误差。
如：7个数，假设最值为10、80，如果使用6个桶，则桶的大小为70/6=11.66，每个桶分别为：
[10,21]、 [22,33]、 [34,44]、 [45,56]、 [57,68]、[69,80]，存在大小为12的桶，比理论下界11.66大。
因此，使用N个桶。

Python代码

# 定义桶
class tagSBucket:
    bValid = False
    nMin = nMax = 0

    def Add(self, n):
        if not self.bValid:
            self.nMin = self.nMax = n
            self.bValid = True
        else:
            if self.nMax < n:
                self.nMax = n
            elif self.nMin > n:
                self.nMin = n

# 计算最大间隔
def calc_max_gap(li):
    if li is None:
        return None
    size = len(li)
    if size <= 1:
        return 0

    pBucket = [tagSBucket() for i in li]
    # 求最值
    nMax = li[0]
    nMin = li[0]
    indexList = list(range(size))
    for i in indexList:
        if nMax < li[i]:
            nMax = li[i]
        elif nMin > li[i]:
            nMax = li[i]
    # 依次将数据放入桶中
    delta = nMax - nMin
    for i in indexList:
        nBucket = int(((li[i] - nMin) / delta) * size)
        if nBucket >= size:
            nBucket = size - 1
        pBucket[nBucket].Add(li[i])

    # 计算有效桶的间隔
    nGap = delta / size  # 最小间隔结果
    i = 0  # 首个桶一定是有效的
    p = pBucket[0].nMax  # 记录最小间隔的两个值
    q = pBucket[1].nMin
    for j in indexList:
        if pBucket[j].bValid:
            gap = pBucket[j].nMin - pBucket[i].nMax
            if nGap < gap:
                nGap = gap
                p = pBucket[i].nMax
                q = pBucket[j].nMin
            i = j
    print('最大间隔的两个数为：%d 和 %d , 间隔为：%d' % (p, q, q - p))
    return nGap


if __name__ == '__main__':
    li = [1, 7, 14, 9, 4, 13]
    calc_max_gap(li)

输出结果：
最大间隔的两个数为：9 和 13 , 间隔为：4

参考七月在线