Java1
时间复杂度:$O(nm)$
空间复杂度:$O(nm)$
思路:
顺时针的方向是右下左上,先保持一个方向进行打印,如果下一个点越界或已打印过,就换一个方向。
同时用布尔数组标记访问过的元素,如果下一个点访问过的话,就换一个方向。
class Solution {
public int[] printMatrix(int[][] matrix) {
int n = matrix.length;
if(n == 0) return new int[0];
int m = matrix[0].length;
int[] res = new int[n * m];
boolean[][] st = new boolean[n][m];
final int[] dx = {-1, 0, 1, 0};
final int[] dy = {0, 1, 0, -1};
int x = 0, y = 0, d = 1, len = 0;
for(int i = 0; i < n * m; ++i) {
res[len++] = matrix[x][y];
st[x][y] = true;
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
return res;
}
}
Java2
时间复杂度:$O(nm)$
空间复杂度:$O(1)$
思路:
自定义边界,从$(0, -1)$开始右下左上的赋值
1.如果超过右边界的话,说明当前顶行已访问,上边界+1
2.如果超过下边界的话,说明当前右列已访问,右边界+1
3.如果超过左边界的话,说明当前底行已访问,底边界+1
4.如果超过上边界的话,说明当前左列已访问,左边界+1
并调整至下一个方向
注意:数组每个$i$是在边界内+1的
class Solution {
public int[] printMatrix(int[][] matrix) {
int n = matrix.length;
if(n == 0) return new int[0];
int m = matrix[0].length;
int[] res = new int[n * m];
final int[] dx = {0, 1, 0, -1};
final int[] dy = {1, 0, -1, 0};
int top = 0, bottom = n - 1, left = 0, right = m - 1;
int a = 0, b = -1, d = 0;
for(int i = 0; i < n * m; ) {
int x = a + dx[d], y = b + dy[d];
if(x >= top && x <= bottom && y >= left && y <= right) {
res[i++] = matrix[x][y];
a = x;
b = y;
} else {
if(y > right) ++top;
else if(x > bottom) --right;
else if(y < left) --bottom;
else if(x < top) ++left;
d = (d + 1) % 4;
}
}
return res;
}
}