我有n 個 唯一點 (X,Y) 的輸入，它們介于 0 和 2^32 之間（含）。坐標是整數。
我需要創建一個演算法來查找距離正好為2018的點對數。
我曾考慮過檢查所有其他點，但它會是O(n^2)，我必須讓它更有效率。我還考慮過使用集合或向量，并使用比較器根據與原點的距離對其進行排序，但這根本無濟于事。
那么我怎樣才能有效地做到這一點呢？
uj5u.com熱心網友回復：
有一個斜邊為 2018 的畢達哥拉斯三元組： 1118 2 1680 2 =2018 2。
由于所有坐標都是整數，因此兩點的坐標（X 和 Y）之間唯一可能的差異是 0、1118、1680 和 2018。
查找在 X（或 Y）坐標之間具有給定差異的所有點對是一個簡單的n log n操作。
2018 以外的數字可能需要更多的作業，因為它們可能是多個畢達哥拉斯三元組的成員（例如 2015 是 3 個三元組的斜邊）。如果數字不是以常數形式給出的，而是在運行時提供的，那么您將必須使用該斜邊生成所有三元組。這可能需要一些sqrt(N)努力（N 是斜邊，而不是點數）。可以在數學 stackexchange 上找到一個配方，例如
在最好的情況下，這可能是 O(n*log(n)) 的復雜性，但不要把我放在那個上面。
關于距離計算的另外一個詞：如果你不這樣做，你可能會快得多
dx = p1x - p2x;
dy = p1y - p2y;
if ( sqrt(dx*dx dy*dy) == 2018 ) {
...
}
但
dx = p1x - p2x;
dy = p1y - p2y;
if ( dx*dx dy*dy == 2018*2018 ) {
...
}
平方比取平方根更快。因此，只需將距離的平方與 2018 年的平方進行比較。
uj5u.com熱心網友回復：
讓我給你一個建議：
兩點 (X1, Y1) 和 (X2, Y2) 之間的距離等于：
sqrt((X2 - X1)^2 (Y2 - Y1)^2)
因此，您可能會考慮檢查：
sqrt((X2 - X1)^2 (Y2 - Y1)^2) <= 2018
但是，您可以輕松地將其簡化為：
(X2 - X1)^2 (Y2 - Y1)^2 <= 2018^2 // or:
(X2 - X1)^2 (Y2 - Y1)^2 <= 4072324
在這里，您已經放棄了平方根的計算，這是一個性能殺手。
接下來，有一個簡單的觀察，如果 X 或 Y 坐標彼此之間的距離大于 2018，那么距離肯定會大于 2018，因此，您可以執行以下操作：
boolean close_enough (double X1, Y1, X2, Y2)
{
if ((abs(X2 - X1) > 2018) || (abs(Y2 - Y1) > 2018))
return false;
else
return ((X2 - X1)^2 (Y2 - Y1)^2 <= 4072324);
}
如您所見，性能優化不僅僅是大 O 符號的問題 :-)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422797.html
標籤：
上一篇：最大封閉磁盤
下一篇：計算簡單多邊形的面積