小编典典

在O(n)中运行的数组“最大差异”算法?

algorithm

给定一个由N个整数组成的数组,对该数组进行排序,然后在排序后的数组中找到两个具有最大差的连续数字。

示例–在输入[1,7,3,2]输出上4(排序后的数组为[1,2,3,7],最大差为7-3 = 4)。

算法A O(NlogN)及时运行。

我需要找到一种在功能上与算法A相同的算法,该算法运行时间为O(N)。


阅读 215

收藏
2020-07-28

共1个答案

小编典典

令数组为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)下界。

2020-07-28