Matrix Diagonal Sum Leetcode 솔루션 TutorialCup

차례

문제 정책

Matrix Diagonal Sum 문제에서 정사각형 매트릭스 정수가 주어집니다. 우리는 대각선에 존재하는 모든 요소의 합을 계산해야합니다. 즉, XNUMX 차 대각선과 XNUMX 차 대각선에있는 요소입니다. 각 요소는 한 번만 계산되어야합니다.

예

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]

설명 :

대각선 합계 : 1 + 5 + 9 + 3 + 7 = 25
mat [1] [1] = 5 요소는 한 번만 계산됩니다.

mat = [[1,1,1,1],
       [1,1,1,1],
       [1,1,1,1],
       [1,1,1,1]]

설명 :

Diagonals sum: (1+1+1+1)+(1+1+1+1)=8.

접근

핀

주어진 정사각형 행렬에서 우리는 대각선 요소를 더하고 그 합계를 반환해야합니다.
대각선 요소에 대한 행렬의 인덱스 패턴이 무엇인지 살펴 보겠습니다. 먼저 주 대각선에서 보면 첫 번째 요소는 인덱스 i = 0, j = 0에 있고 다음 요소는 (i + 1, j + 1)에 있습니다. 마찬가지로 마지막 요소는 인덱스 (n-1, n-1)에 있으며 여기서 n은 주어진 정사각형 행렬의 너비입니다. 이 대각선의 모든 지수는 i = j입니다.
따라서 다음과 같이 루프에서이 대각선을 반복 할 수 있습니다.

1. i = 0 및 j = 0을 초기화합니다.
2. 나는 동안 루프를 실행
3. 현재 요소를 추가합니다. i와 j를 모두 1 씩 증가시킵니다.

이제 0 차 대각선을 살펴 보겠습니다. 첫 번째 행의 첫 번째 요소 인덱스는 i = 1, j = n-1입니다. 다음 요소는 (i + 1.j-1,0)에 있습니다. 마찬가지로 마지막 요소는 (n-XNUMX)에 있습니다.
따라서 루프에서이 대각선을 다음과 같이 반복 할 수 있습니다.

1. i = 0 및 j = n-1을 초기화합니다.
2. 나는 동안 루프를 실행 = 0.
3. 현재 요소를 추가합니다 (1 차 대각선에 있지 않은 경우, 즉 i == j). i를 1 씩 증가시키고 j를 XNUMX만큼 감소시킵니다.

마지막으로 두 작업 후 합계를 반환합니다.

실시

Matrix Diagonal Sum Leetcode 솔루션을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int diagonalSum(vector<vector<int>>& mat) 
{
    int n=mat.size();

    int sum=0;
    int i=0,j=0;

    while(i<n)
    {
        sum+=mat[i][j];
        i++;
        j++;
    }

    i=0;
    j=n-1;

    while(i<n)
    {
        if(i!=j)   sum+=mat[i][j];
        i++;
        j--;
    }

    return sum;
}

int main() 
{
    vector<vector<int>> mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
    };
   
    cout<<diagonalSum(mat)<<endl;

  return 0; 
}

Matrix Diagonal Sum Leetcode 솔루션을위한 Java 프로그램

import java.lang.*;

class Rextester
{  
    public static int diagonalSum(int[][] mat) 
    {
        int n=mat.length;
        
        int sum=0;
        int i=0,j=0;
        
        while(i<n)
        {
            sum+=mat[i][j];
            i++;
            j++;
        }
        
        i=0;
        j=n-1;
        
        while(i<n)
        {
          if(i!=j)   sum+=mat[i][j];
            
            i++;
            j--;
        }
        
        return sum;
        
    }
    
    public static void main(String args[])
    {
       int[][] mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
        };
    
       System.out.println(diagonalSum(mat));
   
    }
}

Matrix Diagonal Sum Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

의 위에) : 여기서 N은 N ^ 2 개의 요소를 갖는 정사각형 행렬의 크기입니다. 우리는 두 대각선 요소에서만 순회하므로 시간 복잡도는 대각선에있는 요소의 수 (2 * N), 즉 O (N)와 같습니다.

공간 복잡성

O (1) : 여기서 공간 복잡성은 추가 메모리를 사용하지 않기 때문에 일정합니다.

행렬 대각 합 Leetcode 솔루션