巧用桶排序，解決Leetcode上Hard的最大間距問題

題目 (Leetcode 164)

給定一個無序的數組，找出數組在排序之後，相鄰元素之間最大的差值。比如輸入: [3,6,9,1], 排序後為[1,3,6,9], 輸出max([3-1, 6-3, 9-6]) = 3

思路

間隔分析：令輸入數組nums排好序為 a ，即 sorted(nums):=a=[a0,a1,a2,⋯,an−1]則:

利用桶排序:

因為 ，而桶內的最大間隔嚴格小於 桶容積，最大間隔必然發生在桶之間(可能相鄰，可能跨過某個空桶)。

總結：

• 設置桶容積為max(a)−min(a) / n−1, 桶個數為n
• 遍歷nums獲取每個桶的[最小值，最大值]
• 遍歷桶，獲取最大gap

源碼如下：

<code>def maximumGap(self, nums: List[int]) -> int:
    len_nums = len(nums)
    if len_nums < 2: return 0

    min_n, max_n = min(nums), max(nums)
    bucket_size = (max_n - min_n) / (len_nums - 1)
    if bucket_size == 0: return 0

    n_bucket = len_nums
    buckets = [[float('inf'), -float('inf')] for _ in range(n_bucket)]
    for n in nums:
        i_bucket = int((n - min_n) // bucket_size)
        buckets[i_bucket][0], buckets[i_bucket][1] = min(buckets[i_bucket][0], n), max(buckets[i_bucket][1], n)

    ans, prev_max = 0, float('inf')
    for s, e in buckets:
        if s == float('inf'): continue
        ans, prev_max = max(s - prev_max, ans), e

    return ans/<code>

閱讀更多 平凡科技 的文章

關鍵字: 間距 排序 巧用