如何查找矩陣區域中的最小或最大元素？

對於N×M個矩陣與整數值，什麼是找到區域（X1，Y1）的最小元件的最有效方式（X2，Y2），其中0 < = X1 < = X2 < M和0 < = Y1 < = Y2 < N如何查找矩陣區域中的最小或最大元素？

我們可以假設我們會多次查詢不同的地區。

我想知道是否可以擴展範圍最小查詢方法到這個問題。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

非常簡單的解決方案可以使用最有效的RMQ解決方案（Segment Tree），然後應用行或列明智。

最壞情況的複雜性將是分（N，M）*日誌（MAX（N，M））

但我依然相信我們可以做得更好。

來源

2013-01-09 cirik

這取決於「最有效的方式」是什麼意思。可以最小化查詢時間本身，預處理時間或內存要求。

如果只有查詢時間應該最小化，「最有效的方法」是預先計算所有可能的區域。然後通過返回一些預先計算的值來處理每個查詢。查詢時間是O（1）。內存和預處理時間都很長：O（（NM））。

更實用的是從OP中引用的頁面使用Sparse Table algorithm。該算法準備一個包含所有冪次長度間隔的表格，並使用一對這樣的間隔來處理任何範圍最小查詢。查詢時間是O（1）。內存和預處理時間是O（N log N）。這個算法可以很容易地擴展到二維情況。

Sparse Table algorithm in 2D

剛準備開機的兩所有長和電力的兩高度矩形的桌子，並使用這些矩形四個處理任何範圍最小的查詢。結果是每個矩形的最小四個最小值。查詢時間是O（1）。內存和預處理時間是O（NM * log（N）* log（M））。

本文："Two-Dimensional Range Minimum Queries" by Amihood Amir, Johannes Fischer, and Moshe Lewenstein建議如何將該算法的內存要求和預處理時間減少到幾乎O（MN）。

本文："Data Structures for Range Minimum Queries in Multidimensional Arrays" by Hao Yuan and Mikhail J. Atallah給出了與O（1）查詢時間和O（NM）存儲器和預處理時間不同的算法。

來源

2013-01-10 14:59:02

僞代碼：

function getMax(M, x1, x2, y1, y2) 
    max = M[x1,y1] 
    for x = x1 to x2 do 
     for y = y1 to y2 do 
      if M[x,y] > max then max = M[x, y] 
    return max

這是在輸入的大小，這隻能合理解釋爲矩陣區域（X2 - X1）的大小爲O（n）*（Y2 - Y1）。如果您想要最小值，請將最大值更改爲最小值，並>至<。你不能比O（n）做得更好，即檢查每個可能的元素。假設你有一個比O（n）更快的算法。然後它不檢查所有元素。爲了得到失敗的算法案例，取其中一個未檢查的元素，並用（max + 1）替換它，然後重新運行該算法。

來源

2013-01-09 21:08:59 Patrick87

感謝您陳述顯而易見的內容，但如果它是一組數字並要求範圍內的最小元素，我們可以做得很好。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor – cirik

@Celada我建議你閱讀它。 – cirik

@cirik我不想讀它，它不是我們回答時的問題的一部分。但在你的堅持下，我看着RMQ部分。這完全是關於預處理數組以獲得幫助索引以加快後續查詢的速度。這種預處理索引是一種折衷，它是否值得它取決於您在進行更改之前預期查詢數組/矩陣的次數。如果你從一開始就有這樣的預處理，並且你沒有在你的問題中提及它，*這就是我的意思是你的問題含糊不清。 – Celada

如果沒有關於矩陣內容或其存儲方式的其他信息，除了掃描給定區域中的每個條目之外，不可能提出任何建議。那是O（（x2-x1）*（y2-y1））。你的問題太含糊其詞，

如果您知道矩陣的其他內容，例如，如果您知道元素可能以某種方式排序，那麼您可能會做得更好（概率上講，平均情況下）。

來源

2013-01-09 21:09:16 Celada

哪部分含糊？ – cirik

如何查找矩陣區域中的最小或最大元素？

回答

相關問題