本文共 1645 字,大约阅读时间需要 5 分钟。
class Solution(): def maximumGap(self, nums): """ :type nums: List[int] :rtype: int """ import math if len(nums) <= 1 : return 0 minValue = 2**31-1 maxValue = -2**31 for num in nums: minValue = min(minValue, num) maxValue = max(maxValue, num) bucket_range = (maxValue - minValue) / len(nums) + 1 bucket_num = math.ceil((maxValue - minValue) / bucket_range) + 1 hashmapMax = { } hashmapMin = { } for i in range(len(nums)): bucket_id = (nums[i]-minValue) // bucket_range if not bucket_id in hashmapMax: hashmapMax[bucket_id] = nums[i] hashmapMin[bucket_id] = nums[i] else: hashmapMax[bucket_id] = max(hashmapMax[bucket_id],nums[i]) hashmapMin[bucket_id] = min(hashmapMin[bucket_id],nums[i]) prev = 0 res = 0 for i in range(1,bucket_num): if not i in hashmapMax: continue if not prev in hashmapMax: continue res = max(res, hashmapMin[i] - hashmapMax[prev]) prev = i return res
class Solution(object): def maximumGap(self, nums): """ :type nums: List[int] :rtype: int """ ln=len(nums) if ln<2: return 0 nums.sort() res=0 for i in range(ln-1): res=max(res,nums[i+1]-nums[i]) return res
转载地址:http://zwahj.baihongyu.com/