問題描述
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
問題分析
又是一道hard題梳码，上來直接沒思路呀收捣。
參考了網(wǎng)上的解題報告，是利用桶排序的思想没佑。
最關(guān)鍵的一點(diǎn)是鸵赖，設(shè)數(shù)組中有n個元素务漩，其中最大值為b，最小值為a它褪，則排序后相鄰兩個元素的差值不會小于?(b-a) / (n-1)?饵骨！
因此做法為，設(shè)置桶的大小為size = ?(b-a) / (n-1)?茫打，那么桶的個數(shù)為(b-a) / size + 1居触；遍歷數(shù)組妖混，對每個桶記錄其最大值和最小值；最后遍歷一遍桶轮洋，最大的gap不會出現(xiàn)在桶的內(nèi)部制市，而在桶之間，因此獲得“后一個非空桶的最小值減前一個非空桶的最大值”的最大值弊予，即為要求的值祥楣。
AC代碼
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n < 2:
return 0
b = a = nums[0]
for i in nums:
if i > b:
b = i
if i < a:
a = i
if a == b:
return 0
size = (b-a) / (n-1)
if (b-a) % (n-1) != 0:
size += 1
num = (b-a) / size + 1
bucket_b = [None for i in range(num)]
bucket_a = [None for i in range(num)]
for i in nums:
bucket = (i-a)/size
if not bucket_b[bucket] or i > bucket_b[bucket]:
bucket_b[bucket] = i
if not bucket_a[bucket] or i < bucket_a[bucket]:
bucket_a[bucket] = i
gap = 0
p = 0
while True:
q = p+1
while q < num and not bucket_a[q]:
q += 1
if q == num:
break
if gap < bucket_a[q] - bucket_b[p]:
gap = bucket_a[q] - bucket_b[p]
p = q
return gap
Runtime: 59 ms, which beats 83.05% of Python submissions.
