- 标签:数组、桶排序、基数排序、排序
- 难度:困难
描述:给定一个无序数组
要求:找出数组在排序之后,相邻元素之间最大的差值。如果数组元素个数小于
说明:
- 所有元素都是非负整数,且数值在
$32$ 位有符号整数范围内。 - 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
示例:
- 示例 1:
输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
- 示例 2:
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。
这道题的难点在于要求时间复杂度和空间复杂度为
这道题分为两步:
- 数组排序。
- 计算相邻元素之间的差值。
第 2 步直接遍历数组求解即可,时间复杂度为
- 遍历数组元素,获取数组最大值元素,并取得位数。
- 以个位元素为索引,对数组元素排序。
- 合并数组。
- 之后依次以十位,百位,…,直到最大值元素的最高位处值为索引,进行排序,并合并数组,最终完成排序。
最后,还要注意数组元素个数小于
class Solution:
def radixSort(self, arr):
size = len(str(max(arr)))
for i in range(size):
buckets = [[] for _ in range(10)]
for num in arr:
buckets[num // (10 ** i) % 10].append(num)
arr.clear()
for bucket in buckets:
for num in bucket:
arr.append(num)
return arr
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
arr = self.radixSort(nums)
return max(arr[i] - arr[i - 1] for i in range(1, len(arr)))
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。