如何找到包含一组模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是值的数量的话）。

- Curd

---

v[i]是一个整数吗？还是一个有序对[start_degree, end_degree]？ - mbeckish

v[i] 是一个测量值（整数或实数都可以）。假设所有的值都存储在数组 v 中。 - Curd

目的是什么？也许https://dev59.com/3nRB5IYBdhLWcg3w26t3#491769 与之相关？ - starblue

Answer 1

好的，请看以下翻译：

1. 将所有角度标准化为 [0, N)
2. 按最小值排序角度
3. 找到距离最远的相邻对：
   3.1 你总是需要减去 (下一个 - 上一个)
   3.2 最后一对应该是 (最后一个; 第一个 + N)
4. 认为你需要的就是这个对 - 只使用步骤 3 中找到的相反角度。

我错了吗？换句话说，我的解决方案很明显 - 你只需找到饼干中最大的部分并吃掉它 :) 剩下的部分 - 就是你所需要的。

- Mikhail Churbanov

---

抱歉，我的英语表达能力不够自由 :) 然而——有一些瓶颈——我骗了你，你不能在这个算法中使用Tom Ritter的距离。 (1) 你需要总是减去(next - previous) (2) 最后一对应该是(last; first + N) - Mikhail Churbanov

我认为，如果您有这个集合：{1，3，359}，您的算法将返回[1, 359]作为最小间隔，而实际上应该是[359，3]。 - Seth

为什么？我们需要循环零 - 因此 [359; 3] - 是4度，而 [1; 359] - 只有两个 - 它更小。没有循环就没有挑战 :) - Mikhail Churbanov

但是 [1, 359] 不包括3 :) - Seth

+1，这是一个非常优雅的解决方案，“找到馅饼中最大的部分并吃掉它”是一个很好的描述。 :-) - ShreevatsaR

Answer 2

我有自己的解决方案，但是我并不完全满意，因为它假设d永远不会大于N/4：

if(v[0]>=N/4 && v[0]<(3*N)/4)
{
  calculate min and max of all v[i]
  c = (max + min)/2;   
  d = (max - min)/2;
}
else
{
  calculate min and max of all (v[i] + N/2) % N
  c = ((max + min)/2 - N/2; 
  d = ((max - min)/2 - N/2;
}

是否有更好的解决方案，特别是如果 d 大于 N/4 时仍能适用的方案？

- Curd

Answer 3

你的问题似乎等同于找到两个角度之间的最大距离。

你只需要遍历你的v集合，计算每个元素之间的距离，然后找到最大的距离即可。

你可以尝试使用以下代码作为你的距离函数：

void dist_mod_360(int a, int b)
{
    const int n = 360; 
    return min((a - b) % n, (b - a) % n);
}

- Seth

---

不，我的距离函数很好，而且它运行得非常完美（也接近于0和360）。我正在寻找的是一个好的（理想情况下是O(n)）算法来找到c和d。 - Curd

猜测您的意思是“计算每对元素之间的距离”。好的。这正是Mihail提出的内容。然而，如果n是值的数量，则这需要O(n*(n-1))的时间复杂度。 - Curd

Answer 4

angle = max(v) - min(v)
return angle if angle <=180 else 360 - angle # to get the smallest absolute value

- Paddy3118