Contents

[Golang][Leetcode][Array]刷題系列-54-Spiral Matrix


54. Spiral Matrix


Level : Medium

原題連結 : Click

題目 :

Given an m x n matrix, return all elements of the matrix in spiral order.


Example :

Note

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]


以下是我自己的解法 - O(m*n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Spiral Matrix.

解題思路 :

  • 這題與59題非常類似
  • 首先題目要求螺旋式的從2D matrix中取出element
  • 這個題目沒有特別的解法就是純粹需要設定好 “邊界條件” & “堅持循環不變量原則(與binary search相同)”
  • 所以需要模擬順時針填入矩陣的過程

解法 :

  • 首先我們可以先規劃出過程
    1. 從左到右
    2. 從上到下
    3. 從右到左
    4. 從下到上
  • 然後我設定每次要走到底才算完成,像是 i = left -> right if left <= right
  • <= 是重點,也就是我們所謂的"堅持循環不變量原則"要定義的原則
  • 且這邊多一個重點就是每一個過程都要判斷是否已經填完m*n個element了
  • 再來想像每次走完一行或一列就很像築起了一道牆,同個方向的路程會 +-1
  • 所以我們要設定4個邊界條件,也根據它們的初始位置跟矩陣的對應對他們賦值,m為row數,n為column數
    1. left = 0
    2. right = n - 1
    3. top = 0
    4. bottom = m - 1
  • 先考慮在執行 1. 的情況,從j = left走到right,然後每個循環都將 res[e] = matrix[top][i]
  • 因為已經成功築起了一道牆,所以top++
  • 先考慮在執行 2. 的情況,從i = top走到bottom,然後每個循環都將 res[e] = matrix[i][right]
  • 因為已經成功築起了一道牆,所以right–
  • 先考慮在執行 3. 的情況,從j = right走到left,然後每個循環都將 res[e] = matrix[bottom][i]
  • 因為已經成功築起了一道牆,所以bottom–
  • 先考慮在執行 4. 的情況,從i = bottom走到top,然後每個循環都將 res[e] = matrix[i][left]
  • 因為已經成功築起了一道牆,所以left++

 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
48
49
50
51
52
53
54
55
func spiralOrder(matrix [][]int) []int {
    
    m := len(matrix)
    n := len(matrix[0])
    
    left, right, top, bottom := 0, n-1, 0, m-1
    
    target := m*n -1
    
    e := -1
    
    res := make([]int, target +1)
    
    for e < target {
        
        for i := left; i <= right && e < target; i++ {
            
            e++
            
            res[e] = matrix[top][i]
        } 
        
        top++
        
        for i := top; i <= bottom && e < target; i++ {
            
            e++
            
            res[e] = matrix[i][right]
        }
        
        right--
        
        for i := right; i >= left && e < target; i-- {
            
            e++
            
            res[e] = matrix[bottom][i]
        } 
        
        bottom--
        
        for i := bottom; i >= top && e < target; i-- {
            
            e++
            
            res[e] = matrix[i][left]
        }
        
        left++
    }
    
    return res
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!