给定一个2D矩阵和一组单元索引，例如（i，j）数组，其中i表示行和j列。对于每个给定的单元索引（i，j），求除第i行和/或第j列中存在的元素之外的所有矩阵元素的和。 例子：
null
mat[][] = { {1, 1, 2} {3, 4, 6} {5, 3, 2} }Array of Cell Indexes: {(0, 0), (1, 1), (0, 1)}Output: 15, 10, 16
我们强烈建议您尽量减少浏览器，并先自己尝试。 A. 天真的解决方案 一次一次地考虑所有给定的细胞指标。对于每个单元索引（i，j），求第i行或第j列中不存在的矩阵元素之和。下面是C++实现的天真方法。
C++
#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 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
# 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#
// 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 */ |
Javascript
<script> // javascript implementation of the approach var R = 3; var C = 3; // A structure to represent a cell index class Cell { constructor(r, c) { this .r = r; this .c = c; } } // A simple solution to find sums for // a given array of cell indexes function printSums(mat, arr , n) { // Iterate through all cell indexes for (i = 0; i < n; i++) { var sum = 0, r = arr[i].r, c = arr[i].c; // Compute sum for current cell index for (j = 0; j < R; j++) { for (k = 0; k < C; k++) { if (j != r && k != c) { sum += mat[j][k]; } } } document.write(sum+ "<br/>" ); } } // Driver code var mat = [ [ 1, 1, 2 ], [ 3, 4, 6 ], [ 5, 3, 2 ] ]; var arr = [ new Cell(0, 0), new Cell(1, 1), new Cell(0, 1) ]; var n = arr.length; printSums(mat, arr, n); // This code is contributed by aashish1995 </script> |
输出：
151016
上述解的时间复杂度为O（n*R*C），其中n是给定单元索引的数量，rxc是矩阵大小。 一 有效解决方案 可以在O（rxc+n）时间内计算所有和。其思想是在处理给定的索引数组之前预计算总和、行和列总和。以下是详细信息 1.计算矩阵的和，称之为和。 2.计算单个行和列的总和。（第[]行和第[]列） 3.对于单元索引（i，j），所需的和将是“和-行[i]–列[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
// 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
# 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 |
Javascript
<script> // An efficient Javascript program to compute // sum for given array of cell indexes var R = 3; var C = 3; // A structure to represent a cell index class Cell { // r is row, varies from 0 to R-1 // c is column, varies from 0 to C-1 constructor(r, c) { this .r = r; this .c = c; } }; function printSums(mat, arr, n) { var sum = 0; var row = Array(R).fill(0); var col = Array(C).fill(0); // Compute sum of all elements, // sum of every row and sum every column for ( var i = 0; i < R; i++) { for ( var 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 ( var i = 0; i < n; i++) { var ro = arr[i].r, co = arr[i].c; document.write(sum - row[ro] - col[co] + mat[ro][co] + "<br>" ); } } // Driver Code var mat = [[1, 1, 2], [3, 4, 6], [5, 3, 2]]; var arr = [ new Cell(0, 0), new Cell(1, 1), new Cell(0, 1)]; var n = arr.length; printSums(mat, arr, n); </script> |
输出：
151016
时间复杂性： O（R x C+n） 辅助空间： O（R+C） 幸亏 高拉夫·阿希瓦 感谢你提出这个有效的解决方案。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
