C ++中矩阵(或2D数组)的前缀和

在这个问题中,我们得到了一个二维整数数组mat [] []。我们的任务是打印mat的前缀和矩阵。

前缀求和矩阵:矩阵的每个元素都是其上下的和元素。即

prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].

让我们以一个例子来了解问题

Input: arr =[

   [4   6   1]

   [5   7   2]

   [3   8   9]

]

Output:[

   [4   10   11]

   [9   22   25]

   [12   33   45]

]

为了解决这个问题,一个简单的解决方案是遍历所有元素直到i,j位置并添加它们,从而找到prefixSum。但这对于系统来说有点复杂。

一个更有效的解决方案是使用公式来查找prefixSum矩阵的元素的值。

ij位置元素的一般公式为

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]

一些特殊情况

For i = j = 0, prefixSum[i][j] = a[i][j]

For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j]

For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]

该代码显示了我们解决方案的实施

示例

#include <iostream>

using namespace std;

#define R 3

#define C 3

void printPrefixSum(int a[][C]) {

   int prefixSum[R][C];

   prefixSum[0][0] = a[0][0];

   for (int i = 1; i < C; i++)

   prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];

   for (int i = 0; i < R; i++)

   prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];

   for (int i = 1; i < R; i++) {

      for (int j = 1; j < C; j++)

      prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];

   }

   for (int i = 0; i < R; i++) {

      for (int j = 0; j < C; j++)

      cout<<prefixSum[i][j]<<"\t";

      cout<<endl;

   }

}

int main() {

   int mat[R][C] = {

      { 1, 2, 3},

      { 4, 5, 6},

      { 7, 8, 9}

   };

   cout<<"The prefix Sum Matrix is :\n";

   printPrefixSum(mat);

   return 0;

}

输出结果

The prefix Sum Matrix is :

1   3   6

5   12   21

12   27   45

以上是 C ++中矩阵(或2D数组)的前缀和 的全部内容, 来源链接: utcz.com/z/338458.html

回到顶部