Javascript: Сумма диагональных и контрдиагональных элементов матрицы n * n


Дана квадратная матрица размера n, вычислите сумму диагональных и контрдиагональных элементов.
где n > 1

Example:
[
  [1, 8, 7],
  [2, 9, 6],
  [3, 4, 5]
]
diagonal = positions [0][0] + [1][1]+ [2][2] => 1+9+5 =15,
counterDiagonal = positions [0][2] + [1][1]+ [3][0] => 7+9+3 =19
Вход в полноэкранный режим Выйти из полноэкранного режима

Сначала попробуем решить задачу методом перебора, а затем оптимизируем ее.

function sumOfDiagonals(matrix) {
  const len = matrix.length;
  let diagonalSum = 0;
  let counterDiagonalSum = 0;
  for (let i = 0; i < len; i++) {
    for (let k = 0; k < len; k++) {
      if (i === k) {
        diagonalSum += matrix[i][k];
      }
      if (i + k == len - 1) {
        counterDiagonalSum += matrix[i][k];
      }

    }
  }

  console.log("sum of diagonal elements --- ", diagonalSum)
  console.log("sum of counter diagonal elements ---", counterDiagonalSum)
}
sumOfDiagonals([
  [1, 8, 7],
  [2, 9, 6],
  [3, 4, 5]
]);
Войти в полноэкранный режим Выход из полноэкранного режима

Приведенное выше решение работает хорошо, но временная и пространственная сложность составляет O(n^2), где n — количество элементов, которые итерировал наш цикл, а мощность 2 — для двух циклов, которые мы использовали.

Давайте попробуем оптимизированное решение:

function sumOfDiagonals(matrix) {
  const len = matrix.length;
  let diagonalSum = 0;
  let counterDiagonalSum = 0;
  for (let i = 0; i < len; i++) {
    diagonalSum += matrix[i][i];
    counterDiagonalSum += matrix[i][len - i - 1];
  }

  console.log("sum of diagonal elements --- ", diagonalSum)
  console.log("sum of counter diagonal elements ---", counterDiagonalSum)
}
sumOfDiagonals([
  [1, 8, 7],
  [2, 9, 6],
  [3, 4, 5]
]);
Войти в полноэкранный режим Выйти из полноэкранного режима

Теперь временная сложность уменьшилась до O(n).

Пожалуйста, ❤️ и поделитесь этим с друзьями или коллегами. Распространяйте знания.


На этом пока все. Продолжайте учиться и верьте в Javascript❤️

Оцените статью
Procodings.ru
Добавить комментарий