题目
给定一个无序数组, 返回其排序后相邻两数差值的最大值.
例如数组元素为 [2, 5, 1, 0], 排序后为[0, 1, 2, 5], 相邻两数差值分别为 [1, 1, 3], 那么就返回3
数组中元素为整数, 范围不定.
要求时间复杂度为 O(n)
思路分析
看过题目后, 首先想到的是先排序, 然后分别计算差值, 返回差值中的最大值即可.
但是又要求时间复杂度为O(n), 比较排序算法都比 O(n)要大的多, 那么剩下桶排序了, 计数排序可以么? 数字范围不定, 计数排序也不行, 但是能达到O(n)的时间复杂度, 也不知道其他的算法啊, 伤脑筋, 那么怎么办呢?
既然计数排序因为数据范围的原因, 不能实现, 那我们能不能根据数据的个数来构建桶呢?
根据数据个数构建桶的思路:
如果有9个数据, 那么就构建9个桶, 将数据范围切分为9等分, 这样就可以按照桶排序将9个数据放到9个桶中, 相邻数的差值就可以求了. 但是, 这样就所有数据的差值都要求, 还要对桶中的数据进行排序, 如此就令时间复杂度又高了. 如何解决这个问题呢?
9个数据, 我们可以构建10个桶啊, 最小的桶和最大的桶中是一定有值的(因为我们是根据数据确定范围的), 那么中间可以保证有一个空桶, 而数据的最大差值就一定是在桶间求得的, 因为空桶两侧的差值最少是桶的范围, 就可以将桶内排除了, 这样桶内只需要保留此范围的最大值于最小值即可, 因为排序后桶间相邻的数就是最大值与最小值.
这样在求差值时, 只要将两桶间的相邻数据进行计算, 然后将计算得出的值中查找最大差值即可, 为什么不只计算空桶两侧的差值呢?
举个例子, 如下图:
好, 基本思路已经明确了, 下面是我简单的代码实现:
简单的桶结构:
算法主体:
计算数据应放入几号桶的式子:
结束!!!
閱讀更多 牛牛的編程之路 的文章
