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

素颜马尾好姑娘i 2022-05-22 10:10 166阅读 0赞

# 最大间隔 #

> 给定整数数组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

参考七月在线