Дано: матрица m x n
Надо: верните все элементы матрицы в спиральном порядке.
Пример 1:
Дано: matrix= [[1,2,3],[4,5,6],[7,8,9]]
Ответ: [1,2,3,6,9,8,7,4,5]
Пример 2:
Дано: matrix= [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Ответ: [1,2,3,4,8,12,11,10,9,5,6,7]
Ограничения:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Решение:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
result = []
start_col, end_col, start_row, end_row = 0, len(matrix[0]) - 1, 0, len(
matrix) - 1
while start_col <= end_col and start_row <= end_row:
for column in range(start_col, end_col + 1):
result.append(matrix[start_row][column])
start_row += 1
for row in range(start_row, end_row + 1):
result.append(matrix[row][end_col])
end_col -= 1
if start_row <= end_row:
for column in range(end_col, start_col - 1, -1):
result.append(matrix[end_row][column])
end_row -= 1
if start_col <= end_col:
for row in range(end_row, start_row - 1, -1):
result.append(matrix[row][start_col])
start_col += 1
return result
ИДЕЯ: вводим переменную result, которая будет содержать список с отсортированными в порядке спирали значениями:
переменные:
- start_col - начальное значение колонки матрицы - первая (0),
- end_col (последняя колонка),
3. start_row (начальное значение строки),
4. end_row (последняя строка матрицы)
Вводим условия запуска перебора, пока не закончатся строки или столбцы:
начинаем перебор:
1) по столбцам, добавляем в результат строку заданной колонки start_row
после меняем значение start_row на следующий ряд
2) по строкам, добавляем все строки последней колонки end_col + 1
после меняем значение end_col на предыдущую колонку
3) проверяем, насколько закрутилась улитка (start_row <= end_row) и начинаем перебор по столбцам в обратном порядке.
4) проверяем, насколько закрутилась улитка (start_col <= end_col) и начинаем перебор по строкам обратном порядке.
Для matrix (в данном случае mat) = [1,2,3], [1,2,3]]
Первый цикл:
Второй цикл:
Третий цикл:
Четвёртый цикл:
Условие if не выполняется, поэтому переходим на новый круг while, который уже тоже выполнен, возвращаем ответ.
Временная сложность: цикл в цикле дают нам O(n*m)
Пространственная сложность. массив даёт нам O(n)