algorithm - 如何在 O(n) 的数组中找到 2 个特殊元素

Question

让a1,...,an是一个实数序列。让m是序列的最小值，令M是序列的最大值。

我证明序列中存在2个元素，x,y , 这样 |x-y|<=(M-m)/n .

现在，有没有办法找到一种算法，它可以在 O(n) 的时间复杂度中找到这样的 2 个元素？ ？

我考虑过对序列进行排序，但由于我对 M 一无所知我不能使用基数/桶或我熟悉的任何其他线性时间算法。

如果有任何想法，我将不胜感激。提前致谢。

Answer 1

1. 先找出n , M , m .如果尚未给出，可以在 O(n) 中确定.

2. 然后创建n+1的内存存储要素；我们将使用存储 n+1宽度为 w=(M-m)/n 的水桶.桶平均覆盖值的范围: Bucket 1来自 [m; m+w[ , 桶 2来自 [m+w; m+2*w[ , 桶 n来自 [m+(n-1)*w; m+n*w[ = [M-w; M[ , 和 (n+1)th来自 [M; M+w[ 的桶.

3. 现在我们遍历所有值并根据分配的间隔将它们分类到桶中。每个桶最多应该有 1 个元素。如果桶已经装满，则意味着元素比半开区间的边界靠得更近，例如我们找到元素 x, y与 |x-y| < w = (M-m)/n .

4. 如果没有找到这样的两个元素，之后n桶 n+1 total 桶装满了一个元素。所有这些元素都已排序。我们再次遍历所有的桶，只比较相邻桶内容的距离，是否有两个元素满足条件。由于桶的宽度，对于不相邻的桶，条件不可能为真:对于那些桶，距离总是 |x-y| > w .

(4. 中最后一个不等式的实现也是为什么区间是半开且不能关闭的原因，也是为什么我们需要 n+1 桶而不是 n 的原因。另一种方法是，使用 n 桶并使用 [M; M+w] 使现在的最后一个桶成为特例。但是 O(n+1)=O(n) 和使用 n+1 步骤比对最后一个桶的特殊外壳更可取。)

运行时间为O(n)对于第 1 步，0对于第 2 步 - 我们实际上没有做任何事情，O(n)对于第 3 步和 O(n)对于第 4 步，因为只有 1每个桶的元素。一共O(n) .

此任务表明，可以在 O(n) 中完成不靠在一起的元素排序或不考虑精细距离的粗排序。而不是 O(n*log(n)) .它有有用的应用程序。计算机上的数字是离散的，它们的精度是有限的。我已经成功地将这种排序方法用于实时生产代码中的信号处理/快速排序。

关于@Damien 的评论:(M-m)/(n-1) 的真实 阈值|对于每个这样的序列都可以证明是正确的。到目前为止，我在答案中假设我们正在查看的序列是一种特殊类型，其中更强的条件为真，或者至少，对于所有序列，如果更强的条件为真，我们将在 O(n) 中找到此类元素。 .

如果这是 OP 的一个小错误(谁说已经证明了更强的条件)，我们应该找到两个元素 x, y与 |x-y| <= (M-m)/(n-1)相反，我们可以简化:

1. -- 3. 我们将像上面那样执行步骤 1 到 3，但是使用 n桶和桶宽度设置为 w = (M-m)/(n-1) .水桶n现在来自 [M; M+w[ .

对于第 4 步，我们将执行以下替代操作:

4./alternative: n每个桶都装满了一个元素。桶中的元素 n必须是 M并且在桶区间的左边界。这个元素的距离y = M到元素 x在n-1th每个这样可能的元素的桶x在n-1th桶是:|M-x| <= w = (M-m)/(n-1) ，所以我们找到了x和 y , 满足条件 q.e.d.