我有一个实数数组 A。它有 n+1 个元素。 已知数组至少有 2 个元素 x 和 y，这样:
abs(x-y) <= (max(A)-min(A))/n
我需要创建一个算法来在 O(n) 时间内找到 2 个项目(如果有更多，任何一对都是好的)。
我已经尝试了几个小时，但还是卡住了，有什么线索/提示吗？
最佳答案
我知道了!诀窍在于 Pigeonhole Principle.
好吧.. 把数字想象成一条线上的点。然后 min(A)和 max(A)分别定义直线的起点和终点。现在将该行分为 n等距长度(max(A)-min(A))/n .因为有n+1点，其中两个必须落入其中一个区间。
请注意，我们不需要依赖问题告诉我们有两点满足标准。 总有两点可以满足。
算法本身:您可以在此处使用桶排序的简化形式，因为每个桶只需要一个项目(点击两个即可完成)。先遍历数组一次得到min(A)和 max(A)并创建一个整数数组 buckets[n]初始化为某个默认值，比如 -1 .然后进行第二遍:
for (int i=0; i<len; i++) {
int bucket_num = find_bucket(array[i]);
if (bucket[bucket_num] == -1)
bucket[bucket_num] = i;
else
// found pair at (i, bucket[bucket_num])
}
在哪里find_bucket(x)返回 x / ((max(A)-min(A))/n) 的向下舍入整数结果.
关于在数组中查找具有给定差异的 2 个项目的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1776574/