54. 螺旋矩阵

image.png

54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

1
2
3
4
5
6
7
输入:
[
[ 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
输入:
[
[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:模拟

直觉

绘制螺旋轨迹路径,我们发现当路径超出界限或者进入之前访问过的单元格时,会顺时针旋转方向。

算法

假设数组有 R 行 C 列,seen[r][c] 表示第 r 行第 c 列的单元格之前已经被访问过了。当前所在位置为 (r, c),前进方向是 di。我们希望访问所有 R x C 个单元格。

当我们遍历整个矩阵,下一步候选移动位置是 (cr, cc)。如果这个候选位置在矩阵范围内并且没有被访问过,那么它将会变成下一步移动的位置;否则,我们将前进方向顺时针旋转之后再计算下一步的移动位置。

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
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length, C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
int r = 0, c = 0, di = 0;
for (int i = 0; i < R * C; i++) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int cr = r + dr[di];
int cc = c + dc[di];
if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
r = cr;
c = cc;
} else {
di = (di + 1) % 4;
r += dr[di];
c += dc[di];
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def spiralOrder(self, matrix):
if not matrix: return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = di = 0
for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans

复杂度分析

  • 时间复杂度: O(N),其中 N 是输入矩阵所有元素的个数。因为我们将矩阵中的每个元素都添加进答案里。
  • 空间复杂度: O(N),需要两个矩阵 seen 和 ans 存储所需信息。

方法 2:按层模拟

直觉

答案是最外层所有元素按照顺时针顺序输出,其次是次外层,以此类推。

算法

我们定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,然后是第 3 层的。

1
2
3
4
5
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}
}

复杂度分析

  • 时间复杂度: O(N),其中 N 是输入矩阵所有元素的个数。因为我们将矩阵中的每个元素都添加进答案里。
  • 空间复杂度: O(N),需要矩阵 ans 存储信息。

方法 3:顺时针旋转

这里的方法不需要记录已经走过的路径,所以执行用时和内存消耗都相对较小

  1. 首先设定上下左右边界
  2. 其次向右移动到最右,此时第一行因为已经使用过了,可以将其从图中删去,体现在代码中就是重新定义上边界
  3. 判断若重新定义后,上下边界交错,表明螺旋矩阵遍历结束,跳出循环,返回答案
  4. 若上下边界不交错,则遍历还未结束,接着向下向左向上移动,操作过程与第一,二步同理
  5. 不断循环以上步骤,直到某两条边界交错,跳出循环,返回答案
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
import java.util.*;

public class Main {

public static void main(String[] args) {
// Scanner in = new Scanner(System.in);
// int n = in.nextInt();
// in.close();
int[][] matrix = new int[][] { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
List<Integer> list = spiralOrder(matrix);
System.out.println(list);
}

static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if (matrix.length == 0)
return list;
int u = 0, d = matrix.length - 1, l = 0, r = matrix[0].length - 1;
while (true) {
// 向右
for (int i = l; i <= r; i++)
list.add(matrix[u][i]);
if (++u > d)
break;
// 向下
for (int i = u; i <= d; i++)
list.add(matrix[i][r]);
if (--r < l)
break;
// 向左
for (int i = r; i >= l; i--)
list.add(matrix[d][i]);
if (--d < u)
break;
// 向上
for (int i = d; i >= u; i--)
list.add(matrix[i][l]);
if (++l > r)
break;
}
return list;
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector <int> ans;
if(matrix.empty()) return ans; //若数组为空,直接返回答案
int u = 0; //赋值上下左右边界
int d = matrix.size() - 1;
int l = 0;
int r = matrix[0].size() - 1;
while(true)
{
for(int i = l; i <= r; ++i) ans.push_back(matrix[u][i]); //向右移动直到最右
if(++ u > d) break; //重新设定上边界,若上边界大于下边界,则遍历遍历完成,下同
for(int i = u; i <= d; ++i) ans.push_back(matrix[i][r]); //向下
if(-- r < l) break; //重新设定有边界
for(int i = r; i >= l; --i) ans.push_back(matrix[d][i]); //向左
if(-- d < u) break; //重新设定下边界
for(int i = d; i >= u; --i) ans.push_back(matrix[i][l]); //向上
if(++ l > r) break; //重新设定左边界
}
return ans;
}
};
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×