Матрицаның қиғаш қосындысының кодының шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Adobe
Array Matrix

Проблемалық мәлімдеме

Матрица диагональды қосындысының квадраты Матрица бүтін сандар берілген. Біз оның диагональдарындағы барлық элементтердің қосындысын есептеуіміз керек, яғни екінші диагональ сияқты бірінші диагональдағы элементтер. Әрбір элементті тек бір рет санау керек.

мысал

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

Түсіндіру:

Диагональдар қосындысы: 1 + 5 + 9 + 3 + 7 = 25
Мат элементі [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.

жақындау

Матрицаның қиғаш қосындысының кодының шешімі

Берілген квадрат матрицада біз тек диагональ элементтерін қосып, оның қосындысын қайтаруымыз керек.
Диагональды элементтер үшін матрицадағы индекстердің қандай болатынын көрейік. Біріншіден, егер біз бірінші диагональдан көрсек, оның бірінші элементі i = 0 индексінде, j = 0, ал келесі элемент (i + 1, j + 1). Сол сияқты соңғы элемент индексте болады (n-1, n-1), онда n - берілген квадрат матрицаның ені. Осы диагональ бойынша барлық индекстерде i = j болады.
Сонымен, біз осы диагональ бойынша цикл бойынша келесідей қайталай аламыз:

1. І = 0 және j = 0 инициализациясы.
2. Мен циклды іске қосыңыз
3. Ағымдағы элементті қосыңыз. I мен j-ді 1-ге көбейту.

Енді екінші диагональды көрейік. бірінші жолдағы бірінші элементтің индексі i = 0, j = n-1. Келесі элемент (i + 1.j-1). Дәл сол сияқты соңғы элемент (n-1,0).
Сонымен, біз осы диагональ бойынша цикл бойынша келесідей қайталай аламыз:

1. І = 0 және j = n-1 инициализациясы.
2. Мен циклды іске қосыңыз = 0.
3. Ағымдағы элементті қосыңыз (егер ол бастапқы диагональға жатпаса, яғни. I == j). I-ді 1-ге, ал j-ді 1-ге көбейту.

Екі операциядан кейін де соманы қайтарыңыз.

Іске асыру

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 Solution үшін күрделілікті талдау

Уақыттың күрделілігі

O (N): Мұнда N - N ^ 2 элементтері бар квадрат матрицаның өлшемі. Біз тек екі диагональды элементтер бойынша жүріп өткендіктен, уақыттың күрделілігі диагональдарда болатын элементтер санына тең болады (2 * N), яғни O (N).

Ғарыштың күрделілігі 

O (1): Бұл жерде кеңістіктің күрделілігі тұрақты, өйткені біз қосымша жадты қолданбаймыз.