如何在O(n)时间复杂度内在数组中找到两个特定元素

Question

假设 a1,...,an 是一组实数序列。令 m 为序列中的最小值，M 为序列中的最大值。

我证明了存在两个元素 x，y 满足 |x-y|<=(M-m)/n。

那么，有没有找到这样的两个元素的算法，其时间复杂度为 O(n)？

我考虑过对序列进行排序，但由于我不知道 M 的大小，因此无法使用基数/桶或其他我熟悉的线性时间算法。

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

- DirichletIsaPartyPooper

---

你知道 M 和 m 吗？解决方案可能是将元素排序到桶中，并存储每个桶的最小和最大元素。 - Sebastian

好的，寻找最小值和最大值需要O(n)时间，使用大小为(M-m)/n的n+1个桶。如果一个桶中有两个元素，则存在匹配项，否则它将是一个桶的最大值和下一个桶的最小值。你可以在第二次运行时检查。这样可以保证复杂度仍然不超过O(n)。 - Sebastian

@Sebastian，你能详细说明一下吗？如何将元素映射到桶中，并保证其中的两个元素被映射到同一个桶中？ - FreeZe

@FreeZe 如果你有两个不同的账户（？），为了清晰起见，最好不要在同一篇帖子中使用它们。 - Damien

请注意，真正的阈值应该是 (M-m)/(n-1)！ - Damien

Answer 1

1. 首先找出n，M，m。如果没有提供，可以在O(n)的时间内确定它们。

2. 然后创建一个包含n+1个元素的内存存储器；我们将使用这个存储器来存储n+1个桶，每个桶的宽度为w=(M-m)/n。 这些桶均等覆盖了值的范围：第一个桶从[m; m+w[开始，第二个桶从[m+w; m+2*w[开始，第n个桶从[m+(n-1)*w; m+n*w[ = [M-w; M[开始，而第n+1个桶从[M; M+w[开始。

3. 接下来，我们遍历所有值，并根据分配的间隔将其排序到相应的桶中。每个桶最多只能有一个元素。如果桶已经被填满，则表示元素之间的距离比半开区间的边界更近，例如我们找到元素x, y使得|x-y| < w = (M-m)/n。

4. 如果找不到这样的两个元素，则之后n个桶中的n+1个总桶会被填充一个元素。然后将所有这些元素进行排序。 我们再次遍历所有桶，并仅比较相邻桶的内容距离，看是否有两个元素满足条件。 由于桶的宽度，对于不相邻的桶，该条件不可能成立：对于那些桶，距离始终为|x-y| > w。

（在第4步中，最后一项不等式的实现也是半开区间无法关闭的原因，以及为什么我们需要n+1个桶而不是n个桶的原因。另一种选择是使用n个桶，并使最后一个桶成为一个特殊情况，即[M; M+w]。但是O(n+1)=O(n)，使用n+1个步骤优于特殊处理最后一个桶。）

步骤1的运行时间为O(n)，步骤2为0——我们实际上在那里什么也没有做，步骤3的运行时间为O(n)，而步骤4的运行时间为O(n)，因为每个桶中只有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)，我们可以简化：

3.我们将像上面一样执行步骤1到3，但使用n个桶和桶宽度设置为w = (M-m)/(n-1)。桶n现在从[M; M+w[开始。

对于第4步，我们将执行以下备选方案：

4./备选方案：n个桶中填充了一个元素。桶n中的元素必须是M，并位于桶间隔的左边界。对于桶n-1中的每个可能元素x，该元素y = M与第n-1个桶中的元素x之间的距离为：|M-x| <= w = (M-m)/(n-1)，因此我们找到了满足条件的x和y，q.e.d。

- Sebastian

Answer 2

首先注意真正的阈值应该是(M-m)/(n-1)。

第一步是在O(N)时间内计算最小的m和最大的M元素。

您需要计算mid = (m + M)/2的值。

将小于mid的值放在数组开头，将大于mid的值放在数组末尾。

选择元素数量最多的那一部分，并迭代直到剩下的数字很少。

如果两个部分具有相同数量的元素，则可以选择其中任何一个。 如果剩余部分的元素比n/2要多得多，则为了保持O（n）复杂度，你只能保留n/2 + 1个元素，因为目标不是找到最小差异，而只是一个足够小的差异。

如@btilly所说的评论中指出，此解决方案在某些情况下可能会失败，例如使用输入[0, 2.1, 2.9, 5]。因此，需要计算左侧最大值和右侧最小值，以检查答案是否不是right_min - left_max。即使解决方案变得不太优雅，也不会改变O（n）的复杂度。

搜索过程的复杂度：O(n) + O(n/2) + O(n/4) + ... + O(2) = O(2n) = O(n)。

- Damien

---

你在这里如何定义密度？ - kcsquared

@kcsquared 我曾将密度定义为给定值区间内数值数量除以该索引区间内总数值数量（n/2，然后是n/4等）。然而，我认为这个算法并不起作用。我很快就会删除这个答案。如果你没有问这个问题，我已经删除了它！ - Damien

有一种类似的分治算法可以使用快速选择来实现。然后，您将数组分成两部分，围绕中位数而不是索引。 - kcsquared

算法可以运行，但它并不像你所说的那样快。如果所有的数字都很接近呢？那么你将会一直除以、除以、除以，并且每次都保留所有的数字！ - btilly

如果剩余部分远大于n/2，那么您不必保留所有元素。至少保留n/2个元素就足够了。OP并没有要求最小差异，只要求差异足够小即可。 - Damien

Answer 3

Damien在他的评论中是正确的，正确的结果是必须存在x、y，使得|x-y| <= (M-m)/(n-1)。如果你有序列[0, 1, 2, 3, 4]，你有5个元素，但没有两个元素之间的距离小于(M-m)/n = (4-0)/5 = 4/5。

通过正确的阈值，解决方案很容易 - 通过一次扫描输入来找到M和m，然后将输入分成(n-1)个大小为(M-m)/(n-1)的桶，将处于一对桶边界上的值放入两个桶中。根据鸽笼原理，至少一个桶中必须有两个值。

- Paul Hankin