无序数组排序后求相邻两数最大值python实现

import sys
def MaxGap(arr):
    if not arr or len(arr)<1:
        return 0
    length = len(arr)
    bucket_num = length+1
    # arr_min = min(arr)
    # arr_max = max(arr)
    arr_min = sys.maxsize
    arr_max = -sys.maxsize
    for  i in range(length):
        if arr[i]<arr_min:
            arr_min = arr[i]
        if arr[i]>arr_max:
            arr_max = arr[i]
    if arr_max == arr_min:
        return 0
    bool_list = [False for i in range(bucket_num)]
    min_list = [0 for i in range(bucket_num)]
    max_list = [0 for i in range(bucket_num)]
    # 有时 True False 0 站位要比 None好一些
    which_bucket = 0
    for i in range(length):
        which_bucket = bucket(arr[i],length,arr_min,arr_max)
        # which_bucket是代表当前数去几号桶 i 表示循环遍历到第几个数
        min_list[which_bucket] = min(min_list[which_bucket],arr[i]) if bool_list[which_bucket] else arr[i]
        #如果进来过数 则比较原来的桶里当前序号的极值与当前值比较，没进来过直接加
        max_list[which_bucket] = max(max_list[which_bucket],arr[i]) if bool_list[which_bucket] else arr[i]
        bool_list[which_bucket] = True
    #要后一个桶的最小减去前一非空桶的最大
    res = 0
    last_max = max_list[0]
    for i in range(1,bucket_num):
        if bool_list[i]:
            res = max(res,min_list[i]-last_max)
            last_max = max_list[i]
    return res

def bucket(a,length,min,max):
    # a 当前元素是几
    #length 数组长度
    #min 数据组最小值
    # 数据组最大值
    #return 去哪个桶
    which_bucket = int((a-min)/int((max-min+1)/(length+1)))
    return which_bucket

if __name__ == '__main__':
    li = [9,3,1,10]
    a = MaxGap(li)
    print(a)

【题目】

给定一个整型数组arr，返回排序后的相邻两数的最大差值 
例如： 
arr = [9, 3, 1, 10]。如果排序，结果为[1, 3, 9, 10]，9和3的差为最大值，故返回6. 
arr = [5, 5, 5, 5]。返回0. 
要求时间复杂度O(N).

【基本思路】

利用桶排序的思想（不是直接进行桶排序），可以做到时间复杂度O(N)，空间复杂度O(N)。

遍历数组arr，找到最大值max和最小值min。如果数组的长度为N，那么我们准备N+1个桶，把max单独放在第N+1个桶里。arr中[min, max)范围上的数放在1～N号桶里。对于1～N个桶，每个桶负责的区间大小为(max- min) / N。所以对于元素num，它应该被分配进的桶的编号是(num - min) / ((max - min) / N) = (num - min) * N / (max - min)，注意：这里的桶的编号是从0开始计数的。 
 
arr一共有N个数，其中min一定会放在1号桶，max一定会放在N+1号桶，所以如果把N个数放入N+1个桶，其中一定有桶是空的。那么差值最大的情况一定不来自同一个桶内的数。所以，如果arr经过排序，最大差值只可能来自某个非空桶的最小值减去前一个非空桶的最大值。