algorithm - 查找无序数组中两个相邻数字之间的最大差异

Question

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

1. 给定一个由 n 个整数组成的无序数组(例如 {3, 5, 1})。
2. “相邻”表示从有序数组 {1, 3, 5} 中选取 2 个数字，并且它们相邻。

如果数组已排序，找出任何一对相邻数字之间的最大差异。不需要确定选择了哪些元素，它们在哪里，或者实际对数组进行排序。

我只能找到一种需要大量内存来存储巨大位图的方法。标记输入中的所有数字，然后扫描位图以查找最大的零串。 (这是一个带重复消除的 Counting Sort，因此对于每个可能的输入数字只需要一个一位饱和计数器。)

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

如果有必要或有帮助，假设整数都是 machine word int，而不是任意整数。

Answer 1

进一步假设数组中整数的大小是有界的，例如可以这样做:

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

或

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