在一个无序数组中找到相邻两个数字之间的最大差值

Question

我正在寻找一种算法，可以在 O(n) 时间内解决以下问题：

1. 给定一个无序的整数数组，长度为 n （例如 {3, 5, 1}）。
2. "相邻的" 意味着从有序数组 {1, 3, 5} 中选择两个数字，并使它们相邻。

找到任意一对相邻数字中差值最大的数字。不需要确定选取哪些元素，它们在哪里，或实际排序数组。

我只能找到一种需要巨大内存空间用于计数的方法。将所有输入中的数字标记在其中，然后扫描比特图以查找最长的零序列。（这是一种去重的 计数排序，因此仅需要对每个可能的输入数字使用一位饱和计数器。）

该比特图解决方案更加适合于 O(n+m) 的情况，其中 m 是所需比特图的大小=最大输入-最小输入。包含 INT_MAX 和 INT_MIN 的小输入数组是该方法的最坏情况。

如果需要或有帮助，请假设整数均为 机器字 int，而不是任意整数。

- Tommy

---

我知道一定有一个O(n)算法来解决这个问题，你是怎么确定的呢？如果你正在寻找“最小差异”，那么这将是元素唯一性问题优化变体，不能使用基于比较的算法在O(n)内解决。 - amit

@Henry 你是正确的，它是O(n + m)。 - Tommy

@amit，我今天在考试中遇到了这个问题，我和我的朋友们都找不到正确的答案。也许问题本身就有问题，我已经编辑了这个问题。 - Tommy

@TagirValeev 这将给你 O(nlogU)，其中 U 是元素的范围。如果范围大于元素数量，则会得到 logn<logU。这只有在存在许多重复项的情况下才有助于渐近复杂度。 - amit

@amit，按照这种推理，每个比较操作的最坏情况都是O(log U)，因为它最多应该比较log U个不同的位。对于减法等数学运算也是一样（应处理log U位）。因此，即使在排序数组中，问题也无法在O(n)内解决。 - Tagir Valeev

Answer 1

假设数组中的整数大小是有限的，可以采取以下措施之一：

1. 对数组进行基数排序-> O(n)
2. 找到最大差异-> O(n)

或者

1. 在数组中查找最小和最大整数 -> O(n)
2. 分配大小为max-min+1的位向量 -> O(1)，因为大小是有限的
3. 设置与数组中的数字对应的所有位 -> O(n)
4. 在位向量中查找最大距离 -> O(1)，因为大小是有限的

- Henry

---

我在更新问题之前没有阅读过这个答案。如果你只是在讨论当n趋近于无穷大时的限制，那么你可以说位图的大小是O(1)，而不是称其为m。对于包括INT_MIN和INT_MAX的小型机器字整数数组，RadixSort和CountingSort之间存在巨大的差异。对于64位整数，位图可能需要2百万个1TB硬盘，因此这使得实现变得可行或不可行。 （是的，我知道网络上的约100k存储服务器只是一个常数倍的开销。:P） - Peter Cordes