用於在類別的二維網格中搜索座標的最佳數據結構

我想搜索2D網格中的座標，其中每個元素存儲水平和垂直座標限制並返回相應的座標。用於在類別的二維網格中搜索座標的最佳數據結構

例如：讓座標要被搜索的BE（15,25）和所述電網（其中，A，B，C，d，E和F是返回值）：

(0,0) - (0,10) - (0,20) - (0,30) 
    | [A] | [B] | [C] | 
(10,0) - (10,10) - (10,20) - (10,30) 
    | [D] | [E] | [F] | 
(20,0) - (20,10) - (20,20) - (20,30) 
    | [G] | [H] | [I] | 
(30,0) - (30,10) - (30,20) - (30,30)

所以，因爲我們的座標（15,25）在10-20垂直和20-30水平之間，搜索功能應該返回[F]。

那麼在這種情況下，哪種數據結構和搜索算法在複雜性方面最好？

注意：水平軸和垂直軸的座標限制已按升序排列。

來源

2017-10-21 Aayush Taneja

什麼是明顯的解決方案？請在你的問題中寫下來，也許我們可以從那裏開始。 –

我很抱歉，但我無法理解你的問題。你能重新框架嗎？ @JohnZwinck –

網格是統一的還是間距可以是任意的？你的網格代表什麼？ –

什麼數據結構？

Array。

一個數組，例如一個元素是2D點。這將是O（n）, where n`是您的軸的大小。

搜索算法？數據已按升序排序。

使用Binary Search。

兩次，每個軸一次，這將保持漸近符號爲O(logn)。

當然，如果滿足20（如果查詢爲15），您將不得不停止搜索，因爲查詢可能不在數組中。所以如果當前元素大於或等於查詢，您想要停止搜索。

PS：如果網格不是正方形，那麼使用kd-tree並搜索最近的鄰居。

來源

2017-10-21 12:41:50 gsamaras

例如，如果我們想要在（0,10,20,30 ...）的數組中搜索15，那麼不會找到二進制搜索返回值，因爲15（10到20之間）但不等於任何值數組中的元素？ @gsamaras –

right @AayushTaneja更新 – gsamaras

謝謝！ @gsamaras –

暫時忽略您在網格上實際使用的座標，並沿着每個軸將它們標記爲0,1,2,3,...。現在你有一個很好的普通數組。

接下來，找出將實際座標轉換爲上一步中定義的僞座標的函數。在你的例子中，這個函數只是整數（或截斷）除以10.你需要小心一點，當座標沒有很好的間隔時，確保函數找到（as你已經畫出了它）單元格的左上角。

現在，您必須對數組進行兩次函數調用和一次查找。其複雜程度取決於您必須編寫以從座標轉換爲僞座標的函數的複雜性，但是我很難理解k的一些小整數值將如何超過O(k)。查找數組中的元素是O(1)。

來源

2017-10-21 12:42:18

用於在類別的二維網格中搜索座標的最佳數據結構

回答

相關問題