題目描述
給定一個包含 m*n 個元素的矩陣（m 行，n 列），請按順時針螺旋順序，傳回矩陣中所有元素
leetcode 第 54 題
https://leetcode-cn.com/problems/spiral-matrix/
示例
示例 1
輸入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
複制
示例 2
輸入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
複制
分析
方法 1 ：模拟周遊
通過示例，我們可以很清晰的知道螺旋矩陣的周遊過程，是以方法 1 中就采用模拟周遊的方法
首先，我們需要定義行和列的方向數組，因為當周遊到矩陣的邊界需要換方向。同時周遊到已經周遊過的元素時也需要換方向，不然就一直在最外層轉圈了，後面會解釋
行的方向數組 int[] dr = {0, 1, 0, -1}
列的方向數組 int[] dc = {1, 0, -1, 0}
下面分别解釋下
| 行方向向量 | 解釋 |
|---|---|
| 往右周遊 | |
| 1 | 往下周遊 |
| 往左周遊 | |
| -1 | 往上周遊 |
| 列方向向量 | 解釋 |
|---|---|
| 1 | 往右周遊 |
| 往下周遊 | |
| -1 | 往左周遊 |
| 往上周遊 |
有了方向向量，還需要有個二維數組記錄已經周遊過的元素坐标 (row，column) ，如果周遊過，該坐标對應的值就是 true
boolean[][] seen = new boolean[row][column]
在做邊界的判斷的同時也要判斷元素是否被通路過，不然不然就一直在最外層轉圈了。我們拿示例 1 舉例子，當周遊到元素 4 時，如果此時不對已經周遊過的元素進行判斷，下一步就會周遊 1，而不是 5，如下圖所示：
對已經周遊過的元素進行判斷
源碼
public static List<Integer> spiralOrder(int[][] matrix) {
if (matrix.length == 0) {
return new ArrayList();
}
int row = matrix.length;
int column = matrix[0].length;
List result = new ArrayList(row * column);
// 方向數組
// 行方向 0：右,1：下,0：左，-1：上
int[] dr = {0,1,0,-1};
// 列方向 1: 右，0：下，-1：左，0：上
int[] dc = {1,0,-1,0};
int r = 0, c = 0, di = 0;
// 标記第 r 行 c 列的單元素被通路過了
boolean[][] seen = new boolean[row][column];
// 周遊整個二維數組即矩陣
for (int i = 0; i < row * column; i++) {
// 将下标對應的元素放到結果集中
result.add(matrix[r][c]);
// 标記 r 行 c 列的元素被通路過了，這個判斷主要用在要換圈的時候，因為如果沒有這個限制，它就不會縮小圈
seen[r][c] = true;
// 下一步移動的候選位置
int nr = r + dr[di];
int nc = c + dc[di];
// 做邊界與是否已經通路過的判斷
if (nr >= 0 && nr < row && nc >= 0 && nc < column && !seen[nr][nc]) {
r = nr;
c = nc;
} else {
// 說明到了邊界了，需要換方向了
di = (di + 1) % 4;
r = r + dr[di];
c = c + dc[di];
}
}
return result;
}
複制
執行結果
方法1執行結果
複雜度分析
時間複雜度：O(n)，需要周遊矩陣中所有的元素
空間複雜度：O(n)，需要用到數組 seen 和 result
方法 2：按層（圈）周遊
我們把這個矩陣像剝洋蔥似的一層一層的剝開，從最外層一直到最裡層，我們通過示例圖看下流程
方法2流程分析
這個方法了解起來比較簡單，值得需要注意的一點是對目前層是否有 4 條邊的判斷即 rowMin < rowMax && columnMin < columnMax，如果不滿足就表示目前層沒有 4 條邊，就不需要周遊下面邊和左面邊
源碼
public static List<Integer> spiralOrder3(int[][] matrix) {
if (matrix.length == 0) {
return new ArrayList();
}
// rowMin 表示目前層行的最小下标 rowMax 表示目前層行的最大下标
int rowMin = 0, rowMax = matrix.length - 1;
// columnMin 表示目前層列的最小下标 columnMax 表示目前層列的最大下标
int columnMin = 0, columnMax = matrix[0].length - 1;
// (rowMin,columnMin) 代表目前層的左上角的坐标 (rowMax,columnMax) 表示目前層右下角的坐标
List result = new ArrayList(matrix.length * matrix[0].length);
while (rowMin <= rowMax && columnMin <= columnMax) {
// 周遊目前層的上面邊的所有元素 行坐标不變，列坐标 column 從 columnMin 到 columnMax
for (int column = columnMin; column <= columnMax; column++) {
result.add(matrix[rowMin][column]);
}
// 周遊目前層的右面邊的所有元素 列坐标不變，行坐标 row 從 rowMin + 1 到 rowMax
for (int row = rowMin + 1; row <= rowMax; row++) {
result.add(matrix[row][columnMax]);
}
// 如果目前層有 4 條邊即滿足條件 rowMin < rowMax && columnMin < columnMax，還要周遊下面邊和左面邊的所有元素
if (rowMin < rowMax && columnMin < columnMax) {
// 周遊目前層的下面邊的所有元素 行坐标不變，列坐标從 columnMax -1 到 columnMin
for (int column = columnMax - 1; column >= columnMin; column--) {
result.add(matrix[rowMax][column]);
}
// 周遊目前層左面邊的所有元素 列坐标不變，行坐标從 rowMax -1 周遊到 rowMin + 1
for (int row = rowMax - 1; row > rowMin; row--) {
result.add(matrix[row][columnMin]);
}
}
// 周遊一層後，周遊下一層，需要更新 rowMin、rowMax、columnMin、columnMax 的坐标
rowMin++;
rowMax--;
columnMin++;
columnMax--;
}
return result;
}
複制
執行結果
方法2執行結果
複雜度分析
時間複雜度：O(n)，需要周遊矩陣中所有的元素
空間複雜度：O(n)，需要用到 result
用過該題作為面試題的公司