Матриця Діагональ Сума Рішення Леткоду  


Рівень складності Легко
Часто запитують у саман
алгоритми масив кодування інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions Матриця

Постановка проблеми  

У матричній задачі діагональної суми квадрат матриця цілих чисел. Ми повинні обчислити суму всіх елементів, присутніх на його діагоналях, тобто елементів як на первинній, так і на вторинній діагоналі. Кожен елемент слід рахувати лише один раз.

Приклад

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.

Підхід  

Матриця Діагональ Сума Рішення ЛеткодуPin

У даній квадратній матриці нам потрібно просто додати діагональні елементи і повернути її суму.
Давайте подивимося, яким буде шаблон індексів у матриці для діагональних елементів. По-перше, якщо ми бачимо на первинній діагоналі, її перший елемент знаходиться на індексі i = 0, j = 0, а наступний елемент - на (i + 1, j + 1). Аналогічно останній елемент буде знаходитись на індексі (n-1, n-1), де n - ширина даної квадратної матриці. Усі індекси на цій діагоналі мають i = j.
Отже, ми можемо перебирати цю діагональ у циклі наступним чином:

1. Ініціалізуйте i = 0 та j = 0.
2. Запустіть цикл, поки i
3. Додайте поточний елемент. Приріст i та j обидва на 1.

Тепер давайте подивимось на вторинну діагональ. індекс першого елемента в першому рядку дорівнює i = 0, j = n-1. Наступним елементом є (i + 1.j-1). Так само останній елемент знаходиться на (n-1,0).
Тож ми можемо виконати ітерацію по цій діагоналі в циклі наступним чином:

Дивись також
Рішення папки журналу сканера Leetcode Solution

1. Ініціалізуйте i = 0 та j = n-1.
2. Запустіть цикл, поки i = 0.
3. Додайте поточний елемент (якщо він не лежить на первинній діагоналі, тобто. I == j). Збільшення i на 1 і зменшення j на 1.

Нарешті поверніть суму після обох операцій.

Реалізація  

Програма C ++ для рішення матричної діагональної суми Leetcode

#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

Програма Java для матричного діагонального рішення Leetcode Solution

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

Аналіз складності рішення матричного діагонального підсумку Leetcode  

Складність часу

O (N): Тут N - розмір квадратної матриці, що має N ^ 2 елементів. Оскільки ми подорожуємо лише по обох діагональних елементах, складність часу буде дорівнює кількості елементів, присутніх на діагоналях (2 * N), тобто O (N).

Складність простору 

O (1): Тут складність простору постійна, оскільки ми не використовуємо зайвої пам'яті.