算法
使用top、bottom、left、right表示边界
当超出某个边界时,调整边界:
- 超出右边界(y > right)时,上边界加1(++top)
- 超出下边界(x > bottom)时,右边界减1(–right)
- 超出左边界(y < left)时,下边界减1(–bottom)
- 超出上边界(x < top)时,左边界加1(++left)
并调整方向:
- 右 -> 下
- 下 -> 左
- 左 -> 上
- 上 -> 右
C++代码
class Solution {
public:
static vector<int> printMatrix(const vector<vector<int>> &matrix) {
vector<int> res;
if (matrix.empty() || matrix.front().empty()) {
return res;
}
const int m = static_cast<int>(matrix.size());
const int n = static_cast<int>(matrix.front().size());
res.resize(m * n);
// 方向: 右, 下, 左, 上
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int d = 0;
int top = 0, bottom = m - 1, left = 0, right = n - 1; // 边界
// 初始位置: (0, -1)
int i = 0, j = -1;
for (int k = 0; k < m * n;) {
const int x = i + dx[d], y = j + dy[d];
if (x >= top && x <= bottom && y >= left && y <= right) {
res[k] = matrix[x][y];
i = x;
j = y;
++k;
} else {
// 调整边界
if (y > right) {
++top;
} else if (x > bottom) {
--right;
} else if (y < left) {
--bottom;
} else /*if (x < top)*/ {
++left;
}
// 调整方向
++d;
d &= 3;
}
}
return res;
}
};
Java代码
class Solution {
public int[] printMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
final int m = matrix.length;
final int n = matrix[0].length;
int[] res = new int[m * n];
// 方向: 右, 下, 左, 上
final int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
int d = 0;
int top = 0, bottom = m - 1, left = 0, right = n - 1; // 边界
// 初始位置: (0, -1)
int i = 0, j = -1;
for (int k = 0; k < m * n; ) {
final int x = i + dx[d], y = j + dy[d];
if (x >= top && x <= bottom && y >= left && y <= right) {
res[k] = matrix[x][y];
i = x;
j = y;
++k;
} else {
// 调整边界
if (y > right) {
++top;
} else if (x > bottom) {
--right;
} else if (y < left) {
--bottom;
} else /*if(x < top)*/ {
++left;
}
// 调整方向
++d;
d &= 3;
}
}
return res;
}
}
Python3代码
class Solution(object):
def printMatrix(self, matrix):
if len(matrix) == 0 or len(matrix[0]) == 0:
return []
m = len(matrix)
n = len(matrix[0])
res = []
# 方向: 右, 下, 左, 上
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
d = 0
# 边界
top = 0
bottom = m - 1
left = 0
right = n - 1
# 初始位置: (0, -1)
i = 0
j = -1
k = 0
while k < m * n:
x = i + dx[d]
y = j + dy[d]
if x >= top and x <= bottom and y >= left and y <= right:
res.append(matrix[x][y])
i = x
j = y
k += 1
else:
# 调整边界
if y > right:
top += 1
elif x > bottom:
right -= 1
elif y < left:
bottom -= 1;
else: # x < top
left += 1;
# 调整方向
d += 1
d &= 3
return res
复杂度
时间复杂度: O(m*n)
空间复杂度: O(1)
这是chatgpt写的吧
19年夏天写的,那时候还没有chatgpt