数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学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 位置的所有元素并对其求前缀和。但这对系统来说有点复杂。
一个更有效的解决办法是使用一个公式来找到前缀和矩阵的元素值。
元素在 i,j 位置的通用公式为
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
更新于： 2020 年 2 月 4 日
4K+ 观看
广告