高级班 01

技巧 —— 舍弃不可能

题目：给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度 O(N)，且要求不能用非基于比较的排序。

流程：

数组中有 n 个数，准备 n+1 桶
先遍历一遍数组找出最小值和最大值，如果两个值相同，直接返回 0
将最小值和最大值的区间等分成 n+1 份，然后再次遍历数组
- 一共 n 个数，但却有 n+1 个桶，这意味着最终一定会有一个桶为空！
- 因为是按照最小值和最大值进行等分，所以最终最左和最右的桶中一定有数字。
- 比如一共 9 个数，最小值 0 最大值 99，则每一桶存储的数字范围是 10，即 0-9, 10-19, ..., 90-99
- 又比如一共 9 个数，最小值 0 最大值 111，则每个桶存储的数字范围是 11.1，即 (0-11.1), (11.1-22.2), ..., (99.9-111)
再次遍历数组，将每个数字放入对应的桶
因为我们只在乎最大差值，所以每个桶都只需要存储该桶内的最小值和最大值。遍历每一个有数字的桶，查看当前桶的最小值和前一个不为空的桶的最大值两者之间的差值，找到最大差值，该差值就是答案

上面的步骤不难，重点在于为什么要设置一个空桶！首先说明一些，差值并不一定是空桶两侧的两个桶的差值。那设置空桶的意义何在和？

答案就是立了一个平凡解，也就是将不可能的答案直接排除掉了！因为一共有 n 个数字，而我们却准备了 n+1 个捅，并且桶的范围是最小值和最大值之间的，这些条件是为了保证差值一定在捅与桶之间，而不会在单个桶之内。这样一来，当我们遍历完两次数字后，那些不可能的数字，也就是在一个桶中既不是最大也不是最小的那些值全部都被舍弃了！

from random import randint
from typing import List

def maxGap(arr):
    if not arr or len(arr) < 2:
        return 0
    def bucket(num, length, min_val, max_val):
        # 确定 num 数字在第几个桶。
        return (num - min_val) * length // (max_val - min_val)

    L = len(arr)
    min_val = float('inf')
    max_val = float('-inf')
    for a in arr:
        min_val = min(min_val, a)
        max_val = max(max_val, a)
    if min == max:
        return 0

    hasNum = [False] * (L + 1)
    maxs = [None] * (L + 1)
    mins = [None] * (L + 1)
    bucket_idx = 0
    for num in arr:
        bucket_idx = bucket(num, L, min_val, max_val)
        mins[bucket_idx] = num if not hasNum[bucket_idx] else min(num, mins[bucket_idx])
        maxs[bucket_idx] = num if not hasNum[bucket_idx] else max(num, maxs[bucket_idx])
        hasNum[bucket_idx] = True

    gap = 0
    last_max = maxs[0]
    for i in range(L+1):
        if hasNum[i]:
            gap = max(gap, mins[i] - last_max)
            last_max = maxs[i]
    return gap


def comparator(arr: List[int]):
    if not arr or len(arr) < 2:
        return 0
    arr.sort()
    gap = float('-inf')
    for i in range(1, len(arr)):
        gap = max(gap, arr[i] - arr[i-1])
    return gap


# 对数器
def main():
    testTime = 500000
    maxSize = 100
    maxValue = 100
    succeed = True

    def generateRandomArray(maxSize, maxValue):
        return [randint(-maxValue, maxValue) for _ in range(maxSize)]
    def copyArray(arr):
        return [*arr]

    for _ in range(testTime):
        arr1 = generateRandomArray(maxSize, maxValue)
        arr2 = copyArray(arr1)
        if maxGap(arr1) != comparator(arr2):
            succeed = False
            break
    print('✔️' if succeed else '❌')

main()

高级班 01 ​

技巧 —— 舍弃不可能 ​

高级班 01

技巧 —— 舍弃不可能