查找矩陣中除給定單元格的行和/或列中的元素以外的所有元素的總和？ · 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) 提出了這種有效的解決方案。