Дана квадратная матрица. Найти сумму элементов на ее диагонали.
Пример:
Input:
matrix =
[[1,2,3],
[4,5,6],
[7,8,9]]
Output: 15
Input:
matrix =
[[1,1,1,1],
[1,1,1,1],
[1,1,1,1],
[1,1,1,1]]
Output: 4
Решение на Java:
public int diagonalSum(int[][] matrix) {
int sum = 0;
int n = matrix.length;
for (int i = 0; i < n; i++) {
sum += matrix[i][i]; // добавляем элементы главной диагонали sum += matrix[i][n - i - 1]; // добавляем элементы побочной диагонали }
if (n % 2 == 1) { // если размерность матрицы нечетная, вычитаем серединный элемент один раз, чтобы избежать двойного подсчета sum -= matrix[n / 2][n / 2];
}
return sum;
}
В данном решении мы проходимся по каждому элементу главной диагонали и побочной диагонали, добавляя значения в переменную sum. Затем, если размерность матрицы нечетная, мы вычитаем центральный элемент один раз, чтобы избежать двойного подсчета. В конце метод возвращает сумму элементов на диагоналях.
Это решение имеет временную сложность O(n), где n - размерность матрицы, и пространственную сложность O(1), так как мы не создаем дополнительных массивов или структур данных.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov