คำนำหน้าผลรวมของเมทริกซ์ (หรืออาร์เรย์ 2 มิติ) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ 2 มิติของค่าจำนวนเต็ม 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]
]

ในการแก้ปัญหานี้ วิธีแก้ปัญหาง่ายๆ วิธีหนึ่งคือค้นหา prefixSum โดยข้ามองค์ประกอบทั้งหมดจนถึงตำแหน่ง i,j และเพิ่มเข้าไป แต่มันค่อนข้างซับซ้อนสำหรับระบบ

วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้สูตรในการค้นหาค่าขององค์ประกอบของ prefixSum matrix

สูตรทั่วไปสำหรับองค์ประกอบที่ตำแหน่ง 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