我在網上看到的在平面上找到最近點對的演算法的大多數實作都有兩個缺陷之一：要么它們無法滿足 O(nlogn) 運行時間，要么它們無法適應某些情況點共享一個 x 坐標。是否需要散列圖（或等價物）才能以最佳方式解決此問題？
粗略地說，有問題的演算法是（根據 CLRS Ch. 33.4）：
- 對于點 P 的陣列，創建額外的陣列 X 和 Y，使得 X 包含 P 中的所有點，按 x 坐標排序，Y 包含 P 中的所有點，按 y 坐標排序。
- 將這些點一分為二 - 放下一條垂直線，將 X 分成兩個陣列，X L和 X R，然后類似地劃分 Y，這樣 Y L包含直線左側的所有點，Y R包含直線右側的所有點線，均按 y 坐標排序。
- 對每一半進行遞回呼叫，將 X L和 Y L傳遞給一個，將 X R和 Y R傳遞給另一個，并在每一半中找到最小距離d 。
- 最后，判斷是否存在距離小于d的分界線左一點右一點的對；通過幾何論證，我們發現對于分界線距離d內的每個點，我們可以采用只搜索接下來的 7 個點的策略，這意味著劃分的子問題的重組只是一個 O(n) 步（即使乍一看，它看起來是n 2 ）。
這有一些棘手的邊緣情況。人們處理這個問題的一種方法是在每個重組步驟（例如這里）對距離分界線的點帶進行排序（例如這里），但已知這會導致 O(nlog 2 n) 解決方案。
人們處理邊緣情況的另一種方法是假設每個點都有一個不同的 x 坐標（例如這里）：注意最接近的片段，如果一個點的 x 坐標在Y 是 <= 該行，否則為 Pyr (Y R )。請注意，如果所有點都位于同一垂直線上，這將導致我們在 C 中寫入陣列的末尾，因為我們將所有n點寫入 Y L。
因此，當點可以具有相同的 x 坐標時，棘手的一點是將 Y 中的點劃分為 Y L和 Y R，具體取決于 Y 中的點p是在 X L還是 X R中。CLRS 中的偽代碼是（為簡潔起見稍作編輯）：
for i = 1 to Y.length
if Y[i] in X_L
Y_L.length = Y_L.length 1;
Y_L[Y_L.length] = Y[i]
else Y_R.length = Y_R.length 1;
Y_R[Y_R.length] = Y[i]
然而，沒有偽代碼，如果我們使用普通陣列，我們沒有一個神奇的函式可以在 O(1) 時間內確定 Y[i] 是否在 X_L 中。如果我們確信所有 x 坐標都是不同的，那么當然 - 我們知道 x 坐標小于分界線的任何東西都在 X L中，因此通過一次比較，我們知道將Y 中的任何點p劃分為哪個陣列. 但是在 x 坐標不一定不同的情況下（例如，在它們都位于同一垂直線上的情況下），我們是否需要哈希圖來確定 Y 中的點是在 X L還是 X R中并且成功將 Y 分解為 Y L和 Y R在 O(n) 時間內？還是有其他策略？
uj5u.com熱心網友回復：
是的，至少有兩種方法在這里有效。
第一個，正如 Bing Wang 建議的那樣，是應用輪換。如果角度足夠小，這相當于在通過 x 比較后通過 y 坐標打破關系，不需要其他數學運算。
二是在G4G上調整演算法，使用線性時間劃分演算法來劃分實體，使用線性時間排序合并來征服它。大概沒有這樣做是因為作者看重排序相對于前面提到的大多數編程語言中的演算法的簡單性。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471194.html
上一篇：遍歷包含三個鍵值對的物件陣列
下一篇：最長子序列：缺少最后一個元素