题目 (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>
分享到:
閱讀更多 平凡科技 的文章
