考慮以下二維鋸齒狀陣列
[0,0] [0,1] [0,2]
[1,0] [1,1]
[2,0] [2,1] [2,2]
假設我想知道某個范圍內的所有元素，例如 [0,0]-[2,0]，我想要所有這些元素的串列，實作這一目標的最佳方法是什么？是否有任何預先存在的演算法可以實作這一目標？
我試圖在 C# 中實作這一點，但沒有比一些 for 回圈更進一步。
下面的示例更好地提供了有關我想要實作的目標的更多詳細資訊。
使用上面定義的陣列，假設起始索引是 [0,0] 并且范圍的結束索引是 [2,1] 我想創建一個方法來回傳該范圍內的所有索引的值.
預期結果將是該方法回傳以下索引的存盤值。[0,0] [0,1] [0,2] [1,0] [1,1] [2,0] [2,1]
uj5u.com熱心網友回復：
如果 2d 陣列是“排序的”，這意味著當你在每個 1d 陣列中從左到右時，y 會增加，而當你從上到下時，x 會增加，你可以找到你需要的第一個點和最后一個點報告使用二進制搜索的總時間O(logn)，然后報告這兩個點之間的每個點，O(k)其中k是您需要報告的點數（請注意，Omega(k)每個演算法的復雜性都將存在）。
如果二維陣列未排序，而您只想輸出對 A 和對 B 之間的所有對：
should_print = False
should_stop = False
for i in range(len(2dArray)):
for j in range(len(2dArray[i]))
should_print = (should_print or (2dArray[i][j] == A))
if should_print:
print(2dArray[i][j])
should_stop = (2dArray[i][j] == B)
if should_stop:
break
if should_stop:
break
如果您只有n一般的 2d 點并且您希望回答“找到給定矩形中的所有點”的查詢，那么有 2 個資料結構可以幫助您 -kd trees和range trees. 這兩種資料結構為您提供了很好的查詢時間，但它們有點復雜。我不確定你目前的水平是多少，但如果你剛剛開始接觸 DS 和演算法，這些資料結構可能有點過頭了。
編輯（關于范圍樹和 kd 樹的一點點）：
首先，我將解釋范圍樹背后的基本概念。讓我們首先嘗試回答一維點的范圍查詢。這很容易 - 只需構建一個 bst（平衡搜索樹），您就可以用它來回答所報告的點數在O(logn k)哪里的查詢。k構建 bst需要O(nlogn)時間，也需要O(n)空間。
現在，讓我們嘗試采用此解決方案并使其適用于 2D。我們將為點的 x 坐標建立一個 bst。對于 bst 中的每個節點，表示byt的子樹中的所有點。現在，對于每個節點，我們將為 points 的 y 坐標構建一個 bst 。tsub(t)tsub(t)
現在，給定一個范圍，我們將使用第一個 bst 找到包含在 x 范圍內的所有子樹，并且對于每個子樹，我們將找到包含在 y 范圍內的所有點（注意，與子樹對應的 bstsub(t)被保存在節點t）。
查詢需要O(log^2n)時間。構建 DS 需要O(nlog^2n)時間，最后，它需要O(nlogn)空間。我會讓你證明這些陳述。隨著更多的作業，查詢時間可以減少到O(logn)，構建時間可以減少到O(nlogn)。你可以在這里閱讀：http ://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5b.pdf 。
現在談談KD樹。這個想法是用一條垂直線分割中間的二維空間，然后用一條水平線分割中間的每一邊，依此類推。這個DS中的查詢時間O(sqrt(n))是，構建時間是O(nlogn)，空間是O(n)。您可以在此處閱讀有關此 DS 的更多資訊：http ://www.cs.uu.nl/docs/vakken/ga/2021/slides/slides5a.pdf
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492029.html