Сложность: medium
Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.
Пример:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
👨💻 Алгоритм:
1⃣Инициализация и подготовка
Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей.
2⃣Итерация по диагоналям
Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы.
3⃣Обработка диагоналей
Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result.
😎 Решение:
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
if not mat or not mat[0]:
return []
N, M = len(mat), len(mat[0])
result = []
for d in range(N + M - 1):
intermediate = []
r = 0 if d < M else d - M + 1
c = d if d < M else M - 1
while r < N and c > -1:
intermediate.append(mat[r][c])
r += 1
c -= 1
if d % 2 == 0:
result.extend(intermediate[::-1])
else:
result.extend(intermediate)
return result
Ставь 👍 и забирай 📚 Базу знаний