algorithm - 查找数组中角度之间的最大差异

Question

我正在处理一些加速度计数据，这些数据是 -180 到 180 之间的值数组。以度数表示角度。

是否有一个聪明的算法来找到任何两个角度之间的最大差异？

Answer 1

确实应该有很多角度才能担心它。但可以肯定的是，你可以击败 O(n^2)

对数组进行排序。用指针a和逐步完成b。首先找到与b成最大角度的a并将其存储到best。然后反复前进一步a，b直到它停止增加差异。您将遍历列表大约 1.5 次，以 O(n) 为界，因为b不能越过a。所以它并不比排序所花费的时间差。

Answer 2

假设角度在 [0, 180] 中为正，如果在 [-180, 0] 中则为负。

扫描列表，执行以下操作：
1 记录最大和最小的正角
2 记录最大和最小的负角
3 如果一个角是正角，则将其转换（让它减去 180）为负角，并标记它一些标志表明它来自转换

对于#1，最大的差异只是最大的角度减去最小的角度。#2 也是如此。

对于#3，首先对角度进行排序。从排序列表的末尾扫描。如果相邻的角度不同（一个来自转换，一个不是），然后计算差异。如果差异是有史以来最小的差异，请记录并继续扫描。完成后，使用 180 - 差值，并将结果作为差值 #3。

现在你有 3 个差异，选择最大的一个。我想这就是答案。

对于复杂性，所有扫描都是 O(n)。对于排序，如果所有角度都是正的或负的，则根本不需要相位#3。如果需要相位#3，我们可以让它有更少的角度。例如，如果列表的正角较少，我们可以将正角转换为负角，反之亦然。排序是 O(nlgn)，但我们可以有更小的 n。

Answer 3

从 RW 教程中得到这个。

它与您想要的相反（返回最小角度），但您可以调整它。

// Returns shortest angle between two angles,
// between -M_PI and M_PI

static inline CGFloat ScalarShortestAngleBetween(const CGFloat a, const CGFloat b)
{
    CGFloat difference = b - a;
    CGFloat angle = fmodf(difference, M_PI * 2);
    if (angle >= M_PI)
    {
        angle -= M_PI * 2;
    }
    return angle;
}