1 题目描述
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。
如果数组元素个数小于 2,则返回 0
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
输入: [10]
输出: 0
解释: 数组元素个数小于 2,因此返回 0。
2 题解
2.1 直观地
直接排序然后进行比较,检验一下快排。
显然这不是它的目的,
nums_len = len(nums)
if nums_len < 2:
return 0
self.quick_sort(nums, 0, nums_len - 1)
max_value = 0
for i in range(1, nums_len):
diff = nums[i] - nums[i - 1]
if max_value < diff:
max_value = diff
return max_value
def partition(self, arr, start, end):
i, j = start, end
tmp = arr[start]
while True:
while i < end and arr[i] <= tmp:
i += 1
while j > start and arr[j] > tmp:
j -= 1
if i >= j:
break
arr[j], arr[i] = arr[i], arr[j]
arr[j], arr[start] = arr[start], arr[j]
return j
def quick_sort(self, nums, start, end):
if start < end:
j = self.partition(nums, start, end)
self.quick_sort(nums, start, j - 1)
self.quick_sort(nums, j + 1, end)