题目描述：
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于2，则返回0。
示例1：
输入：[3, 6, 9, 1]
输出：3
解释：排序后的数组是[1, 3, 6, 9]，其中相邻元素(3, 6)和(6, 9)之间都存在最大差值3。
示例2：
输入：[10]
输出：0
解释：数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
`请尝试在线性时间复杂度和空间复杂度的条件下解决此问题`
解答思路1（快速排序）：
利用快速排序对数组中的元素进行排序，再遍历元素比较元素间的间距，取得最大间距。
快速排序是一种最坏情况时间复杂度为Θ(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它还能够进行原址排序，甚至在虚拟环境中也能很好地工作。
快速排序的运行时间依赖于划分是否平衡，而平衡与否又依赖于划分的元素。如果划分是平衡的，那么快速排序算法性能与归并排序一样。如果划分不平衡，那么快速排序的性能就接近于插入排序了。
快速排序的平均运行时间更接近于其最好情况，只要划分是常数比例的，算法的运行时间总是O(nlgn)。
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0
def QuickSort(nums, l, r):
if l < r:
m = Partition(nums, l, r) # 算法的关键部分，实现对子数组的原址重排
QuickSort(nums, l, m-1)
QuickSort(nums, m+1, r)
def Partition(nums, l, r):
target = nums[r]
i = l - 1
while l < r:
if nums[l] < target:
i += 1
nums[i], nums[l] = nums[l], nums[i]
l += 1
nums[i+1], nums[r] = nums[r], nums[i+1]
return i+1
QuickSort(nums, 0, len(nums)-1)
i = 0
j = 1
maxi = float('-inf')
while j < len(nums):
if nums[j] - nums[i] > maxi:
maxi = nums[j] - nums[i]
i += 1
j += 1
return maxi
存在问题：
不满足题目说明中以线性时间复杂度的要求。
解答思路2（桶）：
对整个数组排序的代价很大，最坏情况下需要让每个元素都和其他所有元素比较。
如果我们不需要比较所有元素对呢？如果我们将元素分类，比如说用桶，这个想法将是可能的。我们只需要比较这些桶即可。
"""
代码来自LeetCode用户gymer
"""
class Solution(object):
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 桶排序
# 参考：https://blog.csdn.net/zxzxzx0119/article/details/82889998
# 设置n+1个桶是为了保证间距最大的两个数被分到不同的桶中
# 因为最大间距 x >= (max_val - min_val) / (n-1)
# 而使用n+1个桶每个桶中数的差值最大为 (max_val - min_val) / n 因此一个桶不可能同时存放间距最大的两个数
if len(nums) < 2:
return 0
min_val, max_val, n = float('inf'), float('-inf'), len(nums)
for i in range(n):
if nums[i] < min_val:
min_val = nums[i]
if nums[i] > max_val:
max_val = nums[i]
if min_val == max_val:
return 0
mins = [0] * (n + 1)
maxs = [0] * (n + 1)
has_num = [False] * (n + 1)
for num in nums:
index = int((num - min_val) * n / (max_val - min_val))
mins[index] = num if not has_num[index] else min(mins[index], num)
maxs[index] = num if not has_num[index] else max(maxs[index], num)
has_num[index] = True
max_len = 0
m = maxs[0]
for i in range(1, n + 1):
if has_num[i]:
curr_len = mins[i] - m
if curr_len > max_len:
max_len = curr_len
m = maxs[i]
return max_len
解答思路3（基数排序）：
基数排序是一种非比较型整数排序算法，其原理是将数据按位切割成不同的数字，然后按每个位数分别比较。
引理8.3(算法导论) 给定n个d位数，其中每一个数位有k个可能的取值。如果RADIX-SORT使用的稳定排序方法耗时Θ(n+k)，那么它就可以在Θ(d(n+k))时间内将这些数排好序。
基数排序可以看成桶排序的扩展，也是用桶来辅助排序。
import math
class Solution:
def maximumGap(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) < 2:
return 0
maxNum = nums[0]
for i in range(1, len(nums)):
if nums[i] > maxNum:
maxNum = nums[i]
location = 1 # 当前排序位置
Sequence = [[] for _ in range(10)] # 构造桶列表，分别存储单个位数0-9的数据
while True:
dd = math.pow(10, location-1)
if maxNum < dd: # 判断是否已将数据排完
break
# 数据入桶
for i in range(len(nums)):
number = int(nums[i] / dd) % 10 # 计算数据在当前排序位置的余数，放入相应桶
Sequence[number].append(nums[i])
# 写回数组
mm = 0
for j in range(10):
size = len(Sequence[j])
for k in range(size):
nums[mm] = Sequence[j][k]
mm += 1
Sequence[j].clear()
location += 1
maxGap = 0
for i in range(1, len(nums)):
maxGap = max(maxGap, nums[i] - nums[i-1])
return maxGap
网友评论