荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
Design a class to process a matrix, and it needs to be able to return the average
for the elements of arbitrary sub-rectangle inside that matrix, in constant time.
wwwyhx 发表于 2011-7-15 16:05 ![]()
use a two dimensional array says "Sum" to record the sum of elements within a rectangle start at (0,0) ended at (i,j) where i < m and j < n.
For every sub rectangle represented by (a,b,c,d):
SumOfRectangle(a,b,c,d) = Sum(c,d)-Sum(c,b-1)-Sum(a-1,d)+Sum(a-1,b-1) if (a>0 && b>0)
SumOfRectangle(a,b,c,d) = Sum(c,d)-Sum(c,b-1) if (a==0 && b>0)
SumOfRectangle(a,b,c,d) = Sum(c,d)-Sum(a-1,d) if (a>0 && b==0)
SumOfRectangle(a,b,c,d) = Sum(c,d) if (a==0 && b==0)
代码:
- class CPreProcessArray
- {
- public:
- CPreProcessArray(int** pArr, int m, int n);
- ~CPreProcessArray();
- float GetAve(int a, int b, int c, int d);
- private:
- int** m_pArrSum;
- int m_nRow;
- int m_nCol;
- };
- inline CPreProcessArray::CPreProcessArray(int **pArr, int m, int n)
- {
- assert(pArr && m>0 && n>0);
- m_nRow = m;
- m_nCol = n;
- m_pArrSum = new int*[m];
- for (int i = 0; i < m; i++)
- m_pArrSum[i] = new int[n];
- for (int i = 0; i < m; i++)
- m_pArrSum[i][0] = pArr[i][0];
- for (int i = 0; i < n; i++)
- m_pArrSum[0][i] = pArr[0][i];
- for (int i = 1; i < m; i++)
- for (int j = 1; j < n; j++)
- m_pArrSum[i][j] = m_pArrSum[i][j-1] + m_pArrSum[i-1][j] + pArr[i][j] - m_pArrSum[i-1][j-1];
- }
- inline CPreProcessArray::~CPreProcessArray()
- {
- for (int i = 0; i < m_nRow; i++)
- delete []m_pArrSum[i];
- delete []m_pArrSum;
- }
- inline float CPreProcessArray::GetAve(int a, int b, int c, int d)
- {
- assert(a > 0 && b > 0 && c > 0 && d > 0 && a <= c && b <= d && c < m_nRow && d < m_nCol);
- int nSum = 0;
- if (0 == a && 0 == b)
- nSum = m_pArrSum[c][d];
- else if (0 == a)
- nSum = m_pArrSum[c][d] - m_pArrSum[c][b-1];
- else if (0 == b)
- nSum = m_pArrSum[c][d] - m_pArrSum[a-1][d];
- else
- nSum = m_pArrSum[c][d] - m_pArrSum[c][b-1] - m_pArrSum[a-1][d] + m_pArrSum[a-1][b-1];
- return ((float)nSum)/((c-a+1) * (d-b+1));
- }
复制代码 |
|