给定N个整数数组,对数组进行排序,并在排序数组中找到具有最大差异的2个连续数字.示例 - 输入[1,7,3,2]输出4(排序数组为[1,2,3,7],最大差异为7-3 = 4).
算法A在O(NlogN)时间内运行.
我需要找到一个与算法A功能相同的算法,它在O(N)时间内运行.
更新:
解决方案:http: //cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf
小智 14
设数组为X,设n =长度(X).将每个元素x放在桶号底层((x - min(X))*(n - 1)/(max(X) - min(X))).每个桶的宽度是(max(X) - min(X))/(n - 1),并且最大相邻差异至少是那么多,因此所讨论的数字在不同的桶中结束.现在我们所要做的就是考虑其中一个是桶i中的最大值的对,另一个是桶j中的min,其中i <j并且(i,j)中的所有桶k都是空的.这是线性时间.
证明我们确实需要地板:让函数为f(X).如果我们可以在线性时间内计算f(X),那么我们肯定可以在线性时间内决定是否
0 <f(X)≤(max(X) - min(X))/(length(X) - 1),
即,X的元素是否均匀分布并且不是全部相同.让这个谓词为P(X).P的支持具有阶乘(长度(X))连通分量,因此代数计算模型的通常Ω(n log n)下界适用.