给定一个由N个整数组成的数组,对该数组进行排序,然后在排序后的数组中找到两个具有最大差的连续数字。
示例–在输入[1,7,3,2]输出上4(排序后的数组为[1,2,3,7],最大差为7-3 = 4)。
[1,7,3,2]
4
[1,2,3,7]
算法A O(NlogN)及时运行。
O(NlogN)
我需要找到一种在功能上与算法A相同的算法,该算法运行时间为O(N)。
令数组为X,令n = length(X)。将每个元素x放入存储区编号为floor((x-min(X))*(n-1)/(max(X)-min(X)))中。每个存储桶的宽度为(max(X)-min(X))/(n-1),最大相邻差至少为该值,因此所讨论的数字会出现在不同存储桶中。现在我们要做的就是考虑一对,其中一个是存储区i中的最大值,另一个是存储区j中的最小值,其中i <j并且(i,j)中的所有存储区k为空。这是线性时间。
我们确实需要底数的证明:让函数为f(X)。如果我们可以在线性时间内计算f(X),那么我们当然可以在线性时间内决定是否
0 <f(X)≤(max(X)-min(X))/(length(X)-1),
也就是说,X的元素是否均匀分布且不完全相同。令此谓词为P(X)。P的支持具有阶乘(length(X))连接的组件,因此适用代数计算模型的通常Ω(n log n)下界。