如何找到包含一组模N的最小区间？

Question

首先是导致我遇到问题的实际应用:

给定一组v[i]在[0,360]度范围内的角度测量值,包含全部的最小间隔是多少v[i]?

注意:间隔可能在两侧,大约在0附近.

问题的抽象描述:

对于一个给定值的v[i],有什么价值c和d,使得

• 为了所有人i:dist(v[i],c) <= d和
• d 尽可能小
• dist(x,y) = abs(((x-y + N/2 + N) mod N) - N/2) ？

这在开放(无限)规模上是微不足道的,其中dist(x,y) = abs(x-y):

calculate max and min of all v[i]
c = (max + min)/2;
d = (max - min)/2;

但是,对于有限尺度(模N)和上面给出的距离定义,找到c和d的最佳方法是什么？

有没有办法做到这一点O(n)(如果n是值的数量)？

Answer 1

嗯,以下怎么样:

1. 将所有角度归一化为[0,N)
2. 排序角度(最小值)
3. 找到最大距离的neigborung对:
   3.1你需要总是减去(next - previous)
   3.2最后一对应该是(last; first + N)
4. 认为这对是你需要的 - 只使用与你在步骤3中找到的相反的角度.

我错了吗？换句话说,我的解决方案是显而易见的 - 你只需要找到馅饼的最大部分并吃掉它......剩下的就是你所需要的.