在阵列中找到具有给定差异的2个项的算法

Question

我得到一个实数的数组,A.它有n + 1个元素.众所周知,阵列中至少有2个元素x和y,这样:

 abs(x-y) <= (max(A)-min(A))/n

我需要创建一个算法,用于在O(n)时间内找到2个项目(如果有更多,任何一对是好的).

我已经尝试了几个小时而且我被卡住了,任何线索/提示？

Answer 1

哇,我明白了!诀窍在于Pigeonhole原则.

好吧..把这些数字想象成一条线.然后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).