dsal 查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

原文： 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++

#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 */

输出：

15
10
16

上述解决方案的时间复杂度为O(n * R * C)，其中n是给定单元格索引的数量，R x C是矩阵大小。

有效的解决方案可以计算O(R x C + n)时间中的所有和。这个想法是在处理给定的索引数组之前预先计算总和，行和列的总和。下面是详细信息：

计算矩阵之和，称为sum。
计算各个行和列的总和。（row[]和col[]）
对于单元格索引(i, j)，所需的总和将为sum = row[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

// 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

输出：

15
10
16

时间复杂度：O(R x C + n)。

辅助空间：O(R + C)。

感谢 Gaurav Ahirwar 提出了这种有效的解决方案。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/34080.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-21》

分类

最近更新

dsal 查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

C++

Java

Python3

C#

C++

Java

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-10-21》

dsal 查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

查找矩阵中除了给定单元格的行和列中的元素以外的所有元素的总和

C++

Java

Python3

C#

C++

Java

Python3

C

留言

联系客服

dsal 查看更多书籍