问题描述：
给定一个数组，求有序后相邻两个数的最大差值，要求时间复杂度为O(n)
并且不能用非基于比较的排序算法
解决思路
我们使用桶排序的思想，但是不对数组进行排序操作
因为我们只需要获取当前数组元素所在桶的序号，并不是真实地将元素插入某个桶中
下面只是模拟的过程：
- 数组 a 中有 n 个元素，则准备 n+1 个桶，将数组的最小值放入 0 号桶，最大值放入 n 号桶
- 将数组剩余的 n-2 个元素按顺序均匀放入剩余的 n-1 个桶中（每个桶中的元素是有序的），则必有一个空桶，
因此要求的最大差值一定不会来自同一个桶的相邻元素之差 - 最大差值一定是相邻两个桶的后一个桶中最小值与前一个桶中最大值之差，相邻两个桶中间可能会有空桶
max_differ_sorted.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-06-16 23:09:23
"""
给定一个数组，求排序之后相邻两个数的最大差值，要求时间复杂度为O(n)
并且不能用非基于比较的排序算法
解决思路
我们使用桶排序的思想，但是不对数组进行排序操作
因为我们只需要获取当前数组元素所在桶的序号，并不是真实地将元素插入某个桶中
下面只是模拟的过程：
1.数组 a 中有 n 个元素，则准备 n+1 个桶，将数组的最小值放入 0 号桶，最大值放入 n 号桶
2.将数组剩余的 n-2 个元素按顺序均匀放入剩余的 n-1 个桶中，则必有一个空桶，
因此要求的最大差值一定不会来自同一个桶的相邻元素之差
3.最大差值一定是相邻两个桶的后一个桶中最小值与前一个桶中最大值之差，相邻两个桶中间可能会有空桶
"""
from util import Util
from sort import Sort
def max_differ_sorted(a):
"""
时间复杂度：O(n)
"""
n = len(a)
if n < 2:
return 0
_max = max(a) #获取最大值
_min = min(a) #获取最小值
# print(_min)
# print(_max)
if _min == _max: #如果最大值等于最小值，则a中所有的数相等
return 0
# 准备三个长度为n+1的列表
# hasNum记录每个桶中是否有数字
# mins记录每个桶中的最小值
# maxs记录每个桶中的最大值
hasNum = [False] * (n+1)
mins = [None] * (n+1)
maxs = [None] * (n+1)
id = 0
for i in range(0, n):
id = bucket(a[i], n, _min, _max) # 获得当前元素属于哪个桶
mins[id] = min(a[i], mins[id]) if hasNum[id] else a[i]
maxs[id] = max(a[i], maxs[id]) if hasNum[id] else a[i]
hasNum[id] = True
# max_differ等于后一个桶最小值与前一个桶最大值之差的最大值
res = 0
lastMax = maxs[0]
for j in range(1, n+1):
if hasNum[j]:
res = max(res, mins[j] - lastMax)
lastMax = maxs[j]
return res
pass
def max_differ_sorted_std(a):
"""
最直接的方法，先排序，再求相邻的最大差值
时间复杂度：平均O(nlogn) > O(n)
"""
n = len(a)
if n < 2:
return 0
Sort.quick_sort(a)
res = 0
for i in range(n-1):
res = max(res, a[i+1] - a[i])
pass
return res
pass
def bucket(x, n, min, max):
"""
x：待放入桶中的数
n：数组的长度
min：数组元素最小值
max：数组元素最大值
"""
return (x - min) * n // (max - min)
pass
def test():
a = Util.gen_randint_list()
max_differ = max_differ_sorted(a)
print(a)
max_differ_std = max_differ_sorted_std(a)
print(a)
print('test: ', end = '')
print(max_differ)
print('std: ', end = '')
print(max_differ_std)
if max_differ_std == max_differ:
print('true')
else:
print('false')
pass
if __name__ == '__main__':
for x in range(10):
test()
pass
util.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-06-11 22:58:30
import random
class Util(object):
"""
工具类
"""
def gen_randint_list(n = 5, min = 0, max = 10):
"""
生成一个随机int型列表
"""
if n < 1 or min > max:
return []
rand_list = []
for i in range(n):
rand_list.append(random.randint(min, max))
return rand_list
pass
测试结果
max_differ_sorted.PNG
