forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
spiral-matrix-ii.py
47 lines (41 loc) · 1.29 KB
/
spiral-matrix-ii.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from __future__ import print_function
# Time: O(n^2)
# Space: O(1)
#
# Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
#
# For example,
# Given n = 3,
#
# You should return the following matrix:
# [
# [ 1, 2, 3 ],
# [ 8, 9, 4 ],
# [ 7, 6, 5 ]
# ]
#
class Solution:
# @return a list of lists of integer
def generateMatrix(self, n):
matrix = [[0 for _ in xrange(n)] for _ in xrange(n)]
left, right, top, bottom, num = 0, n - 1, 0, n - 1, 1
while left <= right and top <= bottom:
for j in xrange(left, right + 1):
matrix[top][j] = num
num += 1
for i in xrange(top + 1, bottom):
matrix[i][right] = num
num += 1
for j in reversed(xrange(left, right + 1)):
if top < bottom:
matrix[bottom][j] = num
num += 1
for i in reversed(xrange(top + 1, bottom)):
if left < right:
matrix[i][left] = num
num += 1
left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
return matrix
if __name__ == "__main__":
print(Solution().generateMatrix(3))
print(Solution().generateMatrix(8))