algorithm - 在 O(n) 中运行的数组 "maximum difference"算法？

Question

给定一个包含 N 个整数的数组，对数组进行排序，并在排序后的数组中找到相差最大的 2 个连续数字。

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

算法 A 在 O(NlogN) 时间内运行。

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

Answer 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 都是空的。这是线性时间。

我们确实需要 floor 的证明:设函数为 f(X)。如果我们可以在线性时间内计算 f(X)，那么我们当然可以在线性时间内决定是否

0 < f(X) ≤ (最大(X) - 最小(X))/(长度(X) - 1),

即 X 的元素是否均匀分布且不完全相同。令此谓词为 P(X)。 P 的支持具有阶乘(长度(X))连通分量，因此适用于代数计算模型的通常 Ω(n log n) 下界。