행렬 대각 합 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 매트릭스조회수 45

문제 정책

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

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

설명 :

대각선 합계 : 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]]
8

설명 :

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

접근

행렬 대각 합 Leetcode 솔루션

주어진 정사각형 행렬에서 우리는 대각선 요소를 더하고 그 합계를 반환해야합니다.
대각선 요소에 대한 행렬의 인덱스 패턴이 무엇인지 살펴 보겠습니다. 먼저 주 대각선에서 보면 첫 번째 요소는 인덱스 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; 
}
25

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));
   
    }
}
25

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

시간 복잡성

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

공간 복잡성 

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

코멘트를 남겨

Translate »
1