動機
- 忘了bucket sort
- 在python用
[0]*n
通常下場都不好,要改用dict - sort還是比較厲害
Problem
Given an integer array nums
, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0
.
You must write an algorithm that runs in linear time and uses linear extra space.
Example 1:
Input: nums = [3,6,9,1]Output: 3Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: nums = [10]Output: 0Explanation: The array contains less than 2 elements, therefore return 0.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 109
Sol
bucket sort就是把list,分堆,放到bucket中
所以這裡要根據數字的範圍,分到array的孔去,就是下面的B_len
但要注意可能是0,像[1,1,1]
class Solution:
def maximumGap(self, nums):
if len(nums) <= 2:
return max(nums)-min(nums)
mi = min(nums)
nums = [n-mi for n in nums]
val_len = max(nums)
B_len = val_len//len(nums)
B_len = B_len if B_len > 0 else 1
Bmax = defaultdict(lambda : float('-inf'))
Bmin = defaultdict(lambda : float('inf'))
for n in nums:
i = n//B_len
Bmax[i] = max(Bmax[i], n)
Bmin[i] = min(Bmin[i], n)
ret,pre = 0,0
for i in range(1,len(nums)+1):
if i in Bmin:
ret = max(ret, Bmin[i]-Bmax[pre])
pre = i
return ret