查找矩阵中除给定单元格的行和/或列中的元素以外的所有元素的总和？ · GeeksForGeeks 中文系列教程

# 查找矩阵中除给定单元格的行和/或列中的元素以外的所有元素的总和？ > 原文： [https://www.geeksforgeeks.org/find-sum-of-all-elements-in-a-matrix-except-the-elements-in-given-row-andor-column-2/](https://www.geeksforgeeks.org/find-sum-of-all-elements-in-a-matrix-except-the-elements-in-given-row-andor-column-2/) 给定 2D 矩阵和一组单元格索引，例如（i，j）的数组，其中 i 表示行和 j 列。对于每个给定的单元格索引（i，j），查找除第 i 行和/或第 j 列中存在的元素之外的所有矩阵元素的和。 **示例**： ``` mat[][] = { {1, 1, 2} {3, 4, 6} {5, 3, 2} } Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)} Output: 15, 10, 16 ``` **我们强烈建议您最小化浏览器，然后自己尝试。** **朴素的解决方案**一次考虑所有给定的单元格索引。对于每个单元格索引（i，j），找到第 i 行或第 j 列均不存在的矩阵元素之和。下面是朴素方法的 C++ 实现。 ## C++ ```cpp #include<bits/stdc++.h> #define R 3 #define C 3 using namespace std; // A structure to represent a cell index struct Cell { int r; // r is row, varies from 0 to R-1 int c; // c is column, varies from 0 to C-1 }; // A simple solution to find sums for a given array of cell indexes void printSums(int mat[][C], struct Cell arr[], int n) { // Iterate through all cell indexes for (int i=0; i<n; i++) { int sum = 0, r = arr[i].r, c = arr[i].c; // Compute sum for current cell index for (int j=0; j<R; j++) for (int k=0; k<C; k++) if (j != r && k != c) sum += mat[j][k]; cout << sum << endl; } } // Driver program to test above int main() { int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}}; int n = sizeof(arr)/sizeof(arr[0]); printSums(mat, arr, n); return 0; } ``` ## Java ```java // Java implementation of the approach class GFG { static int R = 3; static int C = 3; // A structure to represent a cell index static class Cell { int r; // r is row, varies from 0 to R-1 int c; // c is column, varies from 0 to C-1 public Cell(int r, int c) { this.r = r; this.c = c; } }; // A simple solution to find sums for // a given array of cell indexes static void printSums(int mat[][], Cell arr[], int n) { // Iterate through all cell indexes for (int i = 0; i < n; i++) { int sum = 0, r = arr[i].r, c = arr[i].c; // Compute sum for current cell index for (int j = 0; j < R; j++) { for (int k = 0; k < C; k++) { if (j != r && k != c) { sum += mat[j][k]; } } } System.out.println(sum); } } // Driver code public static void main(String[] args) { int mat[][] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; Cell arr[] = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)}; int n = arr.length; printSums(mat, arr, n); } } // This code is contributed by Princi Singh ``` ## Python3 ```py # Python3 implementation of the approach # A structure to represent a cell index class Cell: def __init__(self, r, c): self.r = r # r is row, varies from 0 to R-1 self.c = c # c is column, varies from 0 to C-1 # A simple solution to find sums # for a given array of cell indexes def printSums(mat, arr, n): # Iterate through all cell indexes for i in range(0, n): Sum = 0; r = arr[i].r; c = arr[i].c # Compute sum for current cell index for j in range(0, R): for k in range(0, C): if j != r and k != c: Sum += mat[j][k] print(Sum) # Driver Code if __name__ == "__main__": mat = [[1, 1, 2], [3, 4, 6], [5, 3, 2]] R = C = 3 arr = [Cell(0, 0), Cell(1, 1), Cell(0, 1)] n = len(arr) printSums(mat, arr, n) # This code is contributed by Rituraj Jain ``` ## C# ```cs // C# implementation of the approach using System; class GFG { static int R = 3; static int C = 3; // A structure to represent a cell index public class Cell { public int r; // r is row, varies from 0 to R-1 public int c; // c is column, varies from 0 to C-1 public Cell(int r, int c) { this.r = r; this.c = c; } }; // A simple solution to find sums for // a given array of cell indexes static void printSums(int [,]mat, Cell []arr, int n) { // Iterate through all cell indexes for (int i = 0; i < n; i++) { int sum = 0, r = arr[i].r, c = arr[i].c; // Compute sum for current cell index for (int j = 0; j < R; j++) { for (int k = 0; k < C; k++) { if (j != r && k != c) { sum += mat[j,k]; } } } Console.WriteLine(sum); } } // Driver code public static void Main(String[] args) { int [,]mat = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; Cell []arr = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)}; int n = arr.Length; printSums(mat, arr, n); } } /* This code is contributed by PrinciRaj1992 */ ``` **输出**： ``` 15 10 16 ``` 上述解决方案的时间复杂度为 O（n * R * C），其中 n 是给定单元格索引的数量，R x C 是矩阵大小。有效的**解决方案**可以计算 O（R x C + n）时间中的所有和。这个想法是在处理给定的索引数组之前预先计算总和，行和列的总和。下面是详细信息 1.计算矩阵之和，称为总和。 2.计算各个行和列的总和。（行[]和 col []） 3.对于单元格索引（i，j），所需的总和将为“求和行[i] – col [j] + arr [i] [j]” 以下是上述想法的实现。 ## C++ ``` // An efficient C++ program to compute sum for given array of cell indexes #include<bits/stdc++.h> #define R 3 #define C 3 using namespace std; // A structure to represent a cell index struct Cell { int r; // r is row, varies from 0 to R-1 int c; // c is column, varies from 0 to C-1 }; void printSums(int mat[][C], struct Cell arr[], int n) { int sum = 0; int row[R] = {}; int col[C] = {}; // Compute sum of all elements, sum of every row and sum every column for (int i=0; i<R; i++) { for (int j=0; j<C; j++) { sum += mat[i][j]; col[j] += mat[i][j]; row[i] += mat[i][j]; } } // Compute the desired sum for all given cell indexes for (int i=0; i<n; i++) { int ro = arr[i].r, co = arr[i].c; cout << sum - row[ro] - col[co] + mat[ro][co] << endl; } } // Driver program to test above function int main() { int mat[][C] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; struct Cell arr[] = {{0, 0}, {1, 1}, {0, 1}}; int n = sizeof(arr)/sizeof(arr[0]); printSums(mat, arr, n); return 0; } ``` ## Java ```java // An efficient Java program to compute // sum for given array of cell indexes class GFG { static int R = 3; static int C = 3; // A structure to represent a cell index static class Cell { int r; // r is row, varies from 0 to R-1 int c; // c is column, varies from 0 to C-1 public Cell(int r, int c) { this.r = r; this.c = c; } }; static void printSums(int mat[][], Cell arr[], int n) { int sum = 0; int []row = new int[R]; int []col = new int[C]; // Compute sum of all elements, // sum of every row and sum every column for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { sum += mat[i][j]; col[j] += mat[i][j]; row[i] += mat[i][j]; } } // Compute the desired sum // for all given cell indexes for (int i = 0; i < n; i++) { int ro = arr[i].r, co = arr[i].c; System.out.println(sum - row[ro] - col[co] + mat[ro][co]); } } // Driver Code public static void main(String[] args) { int mat[][] = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; Cell arr[] = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)}; int n = arr.length; printSums(mat, arr, n); } } // This code is contributed by Princi Singh ``` ## Python3 ```py # Python3 implementation of the approach # A structure to represent a cell index class Cell: def __init__(self, r, c): self.r = r # r is row, varies from 0 to R-1 self.c = c # c is column, varies from 0 to C-1 # A simple solution to find sums # for a given array of cell indexes def printSums(mat, arr, n): Sum = 0 row, col = [0] * R, [0] * C # Compute sum of all elements, # sum of every row and sum every column for i in range(0, R): for j in range(0, C): Sum += mat[i][j] row[i] += mat[i][j] col[j] += mat[i][j] # Compute the desired sum # for all given cell indexes for i in range(0, n): r0, c0 = arr[i].r, arr[i].c print(Sum - row[r0] - col[c0] + mat[r0][c0]) # Driver Code if __name__ == "__main__": mat = [[1, 1, 2], [3, 4, 6], [5, 3, 2]] R = C = 3 arr = [Cell(0, 0), Cell(1, 1), Cell(0, 1)] n = len(arr) printSums(mat, arr, n) # This code is contributed by Rituraj Jain ``` ## C# ``` // An efficient C# program to compute // sum for given array of cell indexes using System; class GFG { static int R = 3; static int C = 3; // A structure to represent a cell index public class Cell { public int r; // r is row, varies from 0 to R-1 public int c; // c is column, varies from 0 to C-1 public Cell(int r, int c) { this.r = r; this.c = c; } }; static void printSums(int [,]mat, Cell []arr, int n) { int sum = 0; int []row = new int[R]; int []col = new int[C]; // Compute sum of all elements, // sum of every row and sum every column for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { sum += mat[i, j]; col[j] += mat[i, j]; row[i] += mat[i, j]; } } // Compute the desired sum // for all given cell indexes for (int i = 0; i < n; i++) { int ro = arr[i].r, co = arr[i].c; Console.WriteLine(sum - row[ro] - col[co] + mat[ro, co]); } } // Driver Code public static void Main(String[] args) { int [,]mat = {{1, 1, 2}, {3, 4, 6}, {5, 3, 2}}; Cell []arr = {new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)}; int n = arr.Length; printSums(mat, arr, n); } } // This code is contributed by Rajput-Ji ``` **输出**： ``` 15 10 16 ``` **时间复杂度**： O（R x C + n） **辅助空间**： O（R + C）感谢 [Gaurav Ahirwar](https://www.facebook.com/COOL.DUDE.BORN.NUD3?fref=ts&ref=br_tf) 提出了这种有效的解决方案。