问题描述
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
- 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
- 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
解题思路
基数排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
def radix_sort(nums: List[int]) -> None:
"""基数排序"""
max_val = max(nums)
key = 1
while max_val // key:
# 计数排序
count = [0] * 10
for x in nums:
count[(x // key) % 10] += 1
for i in range(1, len(count)):
count[i] += count[i - 1]
nums_sorted = [0] * len(nums)
# 从后往前遍历是为了保持排序的稳定性
for x in nums[::-1]:
count[(x // key) % 10] -= 1
nums_sorted[count[(x // key) % 10]] = x
nums[::] = nums_sorted.copy()
key *= 10
radix_sort(nums)
ans = -1
for i in range(1, len(nums)):
ans = max(ans, nums[i]-nums[i-1])
return ans
|
桶排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
min_val, max_val = min(nums), max(nums)
bucket_size = max(1, (max_val - min_val) // (len(nums) - 1))
bucket_num = (max_val - min_val) // bucket_size + 1
buckets = [[float("INF"), -float("INF")] for _ in range(bucket_num)]
for x in nums:
i = (x - min_val) // bucket_size
buckets[i][0] = min(x, buckets[i][0])
buckets[i][1] = max(x, buckets[i][1])
ans = 0
prev = -1
for i in range(bucket_num):
if buckets[i][0] == float("INF"):
continue
if prev != -1:
ans = max(ans, buckets[i][0] - buckets[prev][1])
prev = i
return ans
|