59. Spiral Matrix II

發表於 更新於 分類於 ， 閱讀次數： Disqus： 文章字數： 262

種類 : list
難度 : medium
題目 : 59. Spiral Matrix II

思維邏輯

  1. 向右逐一填充
  2. 向下逐一填充
  3. 向左逐一填充
  4. 向上逐一填充(避免蓋過原點)
  5. 更新起點
  6. 若陣列為奇數，填充中心點

解法

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
class Solution:
    def generateMatrix(self, num: int):
    # initial list to n x n
    matrix = [[0]*num for _ in range(num)]
    left, right = 0, num-1
    top, bottom = 0, num-1
    count = 1
    while left <= right and top <= bottom:
        for i in range(left, right):        # left -> right
            matrix[top][i] = count
            count +=1
        
        for i in range(top, bottom):        # top -> bottom
            matrix[i][right] = count
            count += 1

        for i in range(right, left, -1):    # right -> left
            matrix[bottom][i] = count
            count += 1
        
        for i in range(bottom, top, -1):    # bottom -> top
            matrix[i][left] = count
            count += 1

        # update new start point
        left += 1
        right -= 1
        top += 1
        bottom -= 1
    
    if num % 2 == 1:    # 奇數陣列中心需額外處理
        mid = num//2
        matrix[mid][mid] = count

    return matrix

時間複雜度: O(n^2)
空間複雜度: O(1)

難點

  1. 填充時，需分為上、下、左、右四個loop
  2. 外部loop的停止時機
  3. 奇數需填充中心點

最佳解法

此為最佳解法