[数据结构][Python][经典题目]无序数组排序后的最大相邻差

小鱼儿 2022-10-02 15:52 191阅读 0赞

# 题目： #

有一个无序整型数组，如何求出数组排序后的任意两个相邻元素的最大差值？

# 解决方案： #

1.循环数组，找到最小值和最大值。

2.若有N个数，就创建N+1个桶来装数，分别为 0号桶，1号桶，2号桶…N号桶 。

3.定义三个大小为N+1的数组。

4.循环原数组， 确定每个数被装入哪个桶。如何确定？–>which = (num-min)\*N/(max-min)，每个桶内只能存放进入该桶的最大值和最小值。

5.循环求后一个桶的最小值减去前一个桶的最大值，即得到最大差值。若是空桶，则跳过。

注释：  
1.一共N个数，N+1个桶，且全局最小值放在第一个桶，全局最大值放在最后一个桶，那么中间必有桶是空桶。

2.空桶的意义：排除最大差值的两个相邻的数在同一个桶中。

空桶左边的桶内差值最大是9，空桶两边最小差值为11（30-19=11），但是并不是空桶两边的差值就是最大，看图中最右边两个桶，他们的差值是19（49-30=19）。因此，空桶的意义在于排除最大差值是在同一个桶中出现。

# 空桶的意义是说明：最大差值不可能是来自同一个桶内的两个数。
    def max_difference(arr):
        max_num = arr[0]  # 最大值取系统最小值
        min_num = arr[0]  # 最小值取系统最大值
        for i in arr:  # 循环arr数组中的每一个数
            max_num = max_num if i < max_num else i
            min_num = min_num if i > min_num else i
        bool_bucket = ["false"] * (len(arr) + 1)
        print(bool_bucket)
        min_bucket = [None] * (len(arr) + 1)
        print(min_bucket)
        max_bucket = [None] * (len(arr) + 1)
        for i in arr:
            which = which_bucket(i, min_num, max_num, len(arr))
            print("wich:",which)
            if bool_bucket[which] == "false":
                min_bucket[which] = i
                print("min_bucket:", min_bucket[which])
                max_bucket[which] = i
                print("max_bucket:", max_bucket[which])
                bool_bucket[which] = "true"
            else:
                min_bucket[which] = min(min_bucket[which], i)
                print("min_b:",min_bucket)
                max_bucket[which] = max(min_bucket[which], i)
                print("max_bu:",max_bucket)
    
        pre_max = max_bucket[0]
        print("pre_max",pre_max)
        ret = 0
        for i in range(1, len(arr) + 1):  # 从第二个桶开始
            if bool_bucket[i] == "true":  # 假设空桶就跳过，利用空桶下一个桶中最小值减去空桶上一个桶的最大值求差值。
                ret = max(ret, (min_bucket[i] - pre_max))
                pre_max = max_bucket[i]
                print("ret",ret)
        return ret
    
    
    # 求数组中的数分配的桶号
    def which_bucket(num, min_num, max_num, len):
        return int((num - min_num) * len / (max_num - min_num))
    
    
    arr = [2, 1, 3, 4, 5, 10, 9]
    print(max_difference(arr))