查找陣列中角度之間的最大差異

我正在使用一些加速度計數據，這些數據是介於-180和180之間的數值數組。以度爲單位表示角度。查找陣列中角度之間的最大差異

有沒有一種巧妙的算法來找出任意兩個角度之間的最大差異？

2013-09-29 wmil

聰明嗎？你的意思是像排序他們，然後採取[1]和[N] –

數據是圓形的，180 = -180。所以找到最小和最大是不夠的。 – wmil

先轉換，然後排序。 –

真的應該有很多角度來擔心它。但是當然，你可以擊敗O（n^2）

排序數組。使用指針a和b。首先找到從a開始的最大角度的b，並將其存儲到best。然後重複提前a一步並且步b，直到它停止增加差異。您將遍歷約150次的清單，以O（n）爲界，因爲b無法跨越a。所以它不會比分類花費的時間更糟糕。

來源

2013-09-29 05:57:00 clwhisk

我認爲你已經在這裏得到了正確的答案，但它可以做更多的解釋，將它從「排序並選擇第一個和最後一個」的建議中分離出來。例如，你可以證明爲什麼對於一個有序數組'A'，如果'A [j]'與'A [i]'有最大的角度差，而'A [k]'與'A [ i + 1]'''k> = j'。這是真正阻止你必須通過O（n^2）對進行搜索的原因。 – beaker

如果角度爲[0，180]，則表示角度爲正，如果角度爲[-180,0]，則表示角度爲負。

掃描列表中，執行如下：
1結果的最大和最小正角度
2記錄最大和最小負角度
3如果角度爲正角度，將其轉換（讓它減去180 ）到負角度，並用一些標記標記以指示它來自轉換

對於＃1，最大的差別就是最大的角度減去最小的角度。所以是＃2。

對於＃3，首先排序角度。從排序列表的末尾掃描。如果相鄰的角度是不同種類的（一個來自轉換，一個不是），然後計算差異。如果差異是有史以來最小的差異，請記錄下來，並繼續掃描。完成後，使用180-差值，並將結果作爲差值＃3。

現在你有3個差異，挑選最大的一個。我認爲這是答案。

對於複雜性，所有掃描都是O（n）。對於分類，如果所有角度都是正值或負值，則根本不需要相位＃3。如果需要階段＃3，我們可以讓它有更少的角度。例如，如果列表的正面角度較小，我們可以將正面轉換爲負面，反之亦然。排序是O（nlgn），但我們可以有更小的n。

來源

2013-09-29 06:15:00 Hong

你也可以跳過轉換，並有兩個掃描儀：一個從正角開始，一個在負角開始。 – Teepeemm

從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; 
}

來源

2013-09-29 07:42:52 DogCoffee

這是錯過了重點。 OP已經可以找到兩個角度之間的差異（我們假設）。我們正在尋找最大的角度返回，希望沒有經過所有成對轉換的顯而易見的'O（n^2）'過程。 – Teepeemm

查找陣列中角度之間的最大差異

回答

相關問題