2014-02-28 53 views
2

我有一個m×n矩陣,並希望能夠計算任意矩形子矩陣的總和。對於給定的矩陣,這將發生多次。我應該使用什麼數據結構?找到矩陣中任意矩形的總和的最快方法

例如,我想找到矩形的總和矩陣

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 

總和爲68

我要做的是積累它逐行:

1 2 3 4 
6 8 10 12 
15 18 21 24 
28 32 36 40 

而且那麼,如果我想找到矩陣的總和,我只需積累28,32,36,40 = 136。只有四個操作,而不是15. 如果我想找到第二和第三行的總和,我只積累15,18,21,24並減去1,2,3,4。 = 6 + 8 + 10 + 12 + 15 + 18 + 21 + 24 = 。 但在這種情況下,我可以用另一種基質,積累這一個由列:

1 3 6 10 
5 11 18 26 
9 19 30 42 
13 27 42 58 

在這種情況下我剛總結和 = 。只有2個操作而不是8個。對於更寬的子矩陣來說,使用第二種方法和矩陣是有效的,對於更高的第一個。我可以以某種方式拆分合並這種方法到一個矩陣?

所以我只是總結角落,減去另外兩個?

回答

7

你幾乎在那裏用你的方法。該解決方案是使用積分圖(又名整體形象):

的核心思想是你做一個穿過你的矩陣和積累,使得「在任何一點的值( x,y)的總和就是(x,y)以上和左邊所有像素的和。「。

然後,您可以在四個查找的同一時間內計算任意矩形內的和。

+0

如果有* sum * sum查詢遍歷整個或部分矩陣,這是有利的。 – mvw

+0

在我的情況下,它是顯着的大數目和 – JohnDow

+0

是否有快速的Java實現?如果我這樣做brute force =>遞歸 - 它非常緩慢。 – JohnDow

0

爲什麼不能用For循環添加它們?

int total = 0; 
for(int i = startRow; i = endRow; i++) 
{ 
    for(int j = startColumn; j = endColumn; j++) 
    { 
     total += array[i][j]; 
    } 
} 

你在哪裏子陣( 「矩形」)將從STARTROW去endRow(寬度)和STARTCOLUMN到ENDCOLUMN(高度)。

+0

如果我想在N = 1000的矩陣NxN中找到100個子矩陣的和呢? – JohnDow

+0

然後你把上面的代碼放到一個名爲 SumSubarray(int startRow,int endRow,int startCol,int endCol) 的函數中,然後爲每個子矩陣調用它,然後添加結果。 – CoryKramer

+0

@JohnDow對於一次計算網絡是正確的。如果你想優化多個子數目在你的問題中提到它(我沒有看到它) – mvw