有效地计算矩阵的对角线总和

原文: https://www.geeksforgeeks.org/efficiently-compute-sums-of-diagonals-of-a-matrix/

给定一个 2D 正方形矩阵,请找到主对角线和辅助对角线中的元素之和。 例如,考虑以下4 X 4输入矩阵。

A00 A01 A02 A03
A10 A11 A12 A13
A20 A21 A22 A23
A30 A31 A32 A33

主对角线由元素A00, A11, A22, A33形成。

  1. 主对角线的条件:行列条件为row = column

    次对角线由元素A03, A12, A21, A30形成。

  2. 次对角线的条件:行列条件为row = numberOfRows - column - 1

示例

Input : 
4
1 2 3 4
4 3 2 1
7 8 9 6
6 5 4 3
Output :
Principal Diagonal: 16
Secondary Diagonal: 20

Input :
3
1 1 1
1 1 1
1 1 1
Output :
Principal Diagonal: 3
Secondary Diagonal: 3

方法 1(O(n ^ 2)

在此方法中,我们使用两个循环,即列循环和行循环,在内部循环中我们检查上述条件:

C++

// A simple C++ program to find sum of diagonals 
#include <bits/stdc++.h> 
using namespace std; 

const int MAX = 100; 

void printDiagonalSums(int mat[][MAX], int n) 
{ 
    int principal = 0, secondary = 0; 
    for (int i = 0; i < n; i++) { 
        for (int j = 0; j < n; j++) { 

            // Condition for principal diagonal 
            if (i == j) 
                principal += mat[i][j]; 

            // Condition for secondary diagonal 
            if ((i + j) == (n - 1)) 
                secondary += mat[i][j]; 
        } 
    } 

    cout << "Principal Diagonal:" << principal << endl; 
    cout << "Secondary Diagonal:" << secondary << endl; 
} 

// Driver code 
int main() 
{ 
    int a[][MAX] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 },  
                    { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; 
    printDiagonalSums(a, 4); 
    return 0; 
} 

Java

// A simple java program to find 
// sum of diagonals 
import java.io.*; 

public class GFG { 

    static void printDiagonalSums(int [][]mat, 
                                         int n) 
    { 
        int principal = 0, secondary = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 

                // Condition for principal 
                // diagonal 
                if (i == j) 
                    principal += mat[i][j]; 

                // Condition for secondary 
                // diagonal 
                if ((i + j) == (n - 1)) 
                    secondary += mat[i][j]; 
            } 
        } 

        System.out.println("Principal Diagonal:"
                                    + principal); 

        System.out.println("Secondary Diagonal:"
                                    + secondary); 
    } 

    // Driver code 
    static public void main (String[] args) 
    { 

        int [][]a = { { 1, 2, 3, 4 }, 
                      { 5, 6, 7, 8 },  
                      { 1, 2, 3, 4 }, 
                      { 5, 6, 7, 8 } }; 

        printDiagonalSums(a, 4); 
    } 
} 

// This code is contributed by vt_m. 

Python3

# A simple Python program to  
# find sum of diagonals 
MAX = 100

def printDiagonalSums(mat, n): 

    principal = 0
    secondary = 0; 
    for i in range(0, n):  
        for j in range(0, n):  

            # Condition for principal diagonal 
            if (i == j): 
                principal += mat[i][j] 

            # Condition for secondary diagonal 
            if ((i + j) == (n - 1)): 
                secondary += mat[i][j] 

    print("Principal Diagonal:", principal) 
    print("Secondary Diagonal:", secondary) 

# Driver code 
a = [[ 1, 2, 3, 4 ], 
     [ 5, 6, 7, 8 ],  
     [ 1, 2, 3, 4 ], 
      [ 5, 6, 7, 8 ]] 
printDiagonalSums(a, 4) 

# This code is contributed  
# by ihritik 

C#

// A simple C# program to find sum 
// of diagonals 
using System; 

public class GFG { 

    static void printDiagonalSums(int [,]mat, 
                                        int n) 
    { 
        int principal = 0, secondary = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) { 

                // Condition for principal 
                // diagonal 
                if (i == j) 
                    principal += mat[i,j]; 

                // Condition for secondary 
                // diagonal 
                if ((i + j) == (n - 1)) 
                    secondary += mat[i,j]; 
            } 
        } 

        Console.WriteLine("Principal Diagonal:"
                                  + principal); 

        Console.WriteLine("Secondary Diagonal:"
                                  + secondary); 
    } 

    // Driver code 
    static public void Main () 
    { 
        int [,]a = { { 1, 2, 3, 4 }, 
                     { 5, 6, 7, 8 },  
                     { 1, 2, 3, 4 }, 
                     { 5, 6, 7, 8 } }; 

        printDiagonalSums(a, 4); 
    } 
} 

// This code is contributed by vt_m. 

PHP

<?php 
// A simple PHP program to 
// find sum of diagonals 
$MAX = 100; 

function printDiagonalSums($mat, $n) 
{ 
    global $MAX; 
    $principal = 0; 
    $secondary = 0; 
    for ($i = 0; $i < $n; $i++)  
    { 
        for ($j = 0; $j < $n; $j++)  
        { 

            // Condition for  
            // principal diagonal 
            if ($i == $j) 
                $principal += $mat[$i][$j]; 

            // Condition for 
            // secondary diagonal 
            if (($i + $j) == ($n - 1)) 
                $secondary += $mat[$i][$j]; 
        } 
    } 

    echo "Principal Diagonal:" ,  
               $principal ,"\n"; 
    echo "Secondary Diagonal:",  
              $secondary ,"\n"; 
} 

// Driver code 
$a = array (array ( 1, 2, 3, 4 ),  
            array ( 5, 6, 7, 8 ),  
            array ( 1, 2, 3, 4 ),  
            array ( 5, 6, 7, 8 )); 
printDiagonalSums($a, 4); 

// This code is contrbuted by ajit 
?> 

输出

Principal Diagonal:18
Secondary Diagonal:18

此代码需要O(n ^ 2)时间和O(1)辅助空间。

方法 2(O(n)):

在此方法中,我们使用一个循环,即用于计算主对角线和辅助对角线之和的循环:

C++

// An efficient C++ program to find sum of diagonals 
#include <bits/stdc++.h> 
using namespace std; 

const int MAX = 100; 

void printDiagonalSums(int mat[][MAX], int n) 
{ 
    int principal = 0, secondary = 0;  
    for (int i = 0; i < n; i++) { 
        principal += mat[i][i]; 
        secondary += mat[i][n - i - 1];         
    } 

    cout << "Principal Diagonal:" << principal << endl; 
    cout << "Secondary Diagonal:" << secondary << endl; 
} 

// Driver code 
int main() 
{ 
    int a[][MAX] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 },  
                     { 1, 2, 3, 4 }, { 5, 6, 7, 8 } }; 
    printDiagonalSums(a, 4); 
    return 0; 
} 

Java

// An efficient java program to find 
// sum of diagonals 
import java.io.*; 
  
public class GFG { 
  
    static void printDiagonalSums(int [][]mat, 
                                        int n) 
    { 
        int principal = 0, secondary = 0;  
        for (int i = 0; i < n; i++) { 
            principal += mat[i][i]; 
            secondary += mat[i][n - i - 1];  
        } 
      
        System.out.println("Principal Diagonal:"
                                   + principal); 
                                     
        System.out.println("Secondary Diagonal:"
                                   + secondary); 
    } 
      
    // Driver code 
    static public void main (String[] args) 
    { 
        int [][]a = { { 1, 2, 3, 4 }, 
                      { 5, 6, 7, 8 },  
                      { 1, 2, 3, 4 }, 
                      { 5, 6, 7, 8 } }; 
      
        printDiagonalSums(a, 4); 
    } 
} 
  
// This code is contributed by vt_m.

Python3

# A simple Python3 program to find 
# sum of diagonals 
MAX = 100
  
def printDiagonalSums(mat, n): 
  
    principal = 0
    secondary = 0
    for i in range(0, n):  
        principal += mat[i][i] 
        secondary += mat[i][n - i - 1] 
          
    print("Principal Diagonal:", principal) 
    print("Secondary Diagonal:", secondary) 
  
# Driver code 
a = [[ 1, 2, 3, 4 ], 
     [ 5, 6, 7, 8 ],  
     [ 1, 2, 3, 4 ], 
     [ 5, 6, 7, 8 ]] 
printDiagonalSums(a, 4) 
  
# This code is contributed 
# by ihritik

C

// An efficient C#program to find 
// sum of diagonals 
using System; 
  
public class GFG { 
  
    static void printDiagonalSums(int [,]mat, 
                                       int n) 
    { 
        int principal = 0, secondary = 0;  
        for (int i = 0; i < n; i++) { 
            principal += mat[i,i]; 
            secondary += mat[i,n - i - 1];  
        } 
      
        Console.WriteLine("Principal Diagonal:"
                                  + principal); 
                                    
        Console.WriteLine("Secondary Diagonal:"
                                  + secondary); 
    } 
      
    // Driver code 
    static public void Main () 
    { 
        int [,]a = { { 1, 2, 3, 4 }, 
                     { 5, 6, 7, 8 },  
                     { 1, 2, 3, 4 }, 
                     { 5, 6, 7, 8 } }; 
                       
        printDiagonalSums(a, 4); 
    } 
} 
  
// This code is contributed by vt_m.

PHP

<?php 
// An efficient PHP program  
// to find sum of diagonals 
$MAX = 100; 
  
function printDiagonalSums($mat, $n) 
{ 
    global $MAX; 
    $principal = 0; $secondary = 0;  
    for ($i = 0; $i < $n; $i++)  
    { 
        $principal += $mat[$i][$i]; 
        $secondary += $mat[$i][$n - $i - 1];      
    } 
  
    echo "Principal Diagonal:" , 
               $principal ,"\n"; 
    echo "Secondary Diagonal:" ,  
               $secondary ,"\n"; 
} 
  
// Driver Code 
$a = array(array(1, 2, 3, 4), 
           array(5, 6, 7, 8),  
           array(1, 2, 3, 4), 
           array(5, 6, 7, 8)); 
printDiagonalSums($a, 4); 
  
// This code is contributed by aj_36  
?>

输出:

Principal Diagonal:18
Secondary Diagonal:18

此代码需要O(n)时间和O(1)辅助空间。