0

多くの値の非常に大きな配列があり、row-major 1d array.

ex:  
   1 2 3  
   4 5 6

に格納されますint* array = {1,2,3,4,5,6};

私がしなければならないことは、 が与えられrow1, row2, column1, column2、次に面積の合計を出力することです。これにより、さまざまな面積を何度も計算するように要求されます。

私が考えているのは、最初にネストされたループを使用して配列をトラバースし、各行の合計を格納しsum_row、各列の合計sum_columnを格納し、合計要素の合計 im を格納することtotalSumです。

それからtotalSum - the row and the columns that surrond it + the elemnts that has been minus twice。

しかし、それは十分に速いようです。より高速に実行できるアルゴリズムや、係数を小さくできるコーディングスタイルのヒントはありますか?

事前にThx。

4

1 に答える 1

1

ある二重反復を別の反復に置き換えたようです。問題は " " の減算にthe elemnts that has been minus twiceあります。私が間違っていない限り、これにはそれらの要素を繰り返し処理して合計することが含まれます。

代わりに、合計する必要がある長方形の領域を反復するだけです。これ以上遅くなるとは思えません。

加算された左上行列の行列を生成することにより、より効率的なアルゴリズムを得ることができます。(総面積表に関するウィキペディアの記事を参照してください。) 次に、4 つの面積の合計を調べることで、部分行列の合計を計算できます。

于 2013-03-17T16:15:27.160 に答える