剑指 Offer 29. 顺时针打印矩阵
本问题对应的 leetcode 原文链接：剑指 Offer 29. 顺时针打印矩阵
问题描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return new int[0];
}
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1;
int[] res = new int[(r+1) * (b+1)];
int k = 0;
while(true){
// 从左到右
for(int i = t,j = l; j <= r; j++){
res[k++] = matrix[i][j];
}
if(++t > b) break;
// 从下往上
for(int i = t, j = r; i <= b; i++){
res[k++] = matrix[i][j];
}
if(l > --r) break;
// 从右往左
for(int i = b, j = r; j >= l; j--){
res[k++] = matrix[i][j];
}
if(t > --b) break;
// 从下往上
for(int i = b, j = l; i >= t; i--){
res[k++] = matrix[i][j];
}
if(++l > r) break;
}
return res;
}
}
时间复杂度：O(n*m)
额外空间复杂度：O(1)
Python
class Solution(object):
def spiralOrder(self, matrix):
if not matrix or not matrix[0]:
return []
l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
res, k = [], 0
while True:
# 从左到右
for j in range(l, r+1):
res.append(matrix[t][j])
k += 1
if t+1 > b:
break
else:
t += 1
# 从上到下
for i in range(t, b+1):
res.append(matrix[i][r])
k += 1
if r-1 < l:
break
else:
r -= 1
# 从右到左
for j in range(r, l-1, -1):
res.append(matrix[b][j])
k += 1
if b-1 < t:
break
else:
b -= 1
# 从下到上
for i in range(b, t-1, -1):
res.append(matrix[i][l])
k += 1
if l+1 > r:
break
else:
l += 1
return res
C++
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) {
return {};
}
int l = 0, r = matrix[0].size() - 1, t = 0, b = matrix.size() - 1;
vector<int> res;
while (true) {
// 从左到右
for (int j = l; j <= r; ++j) {
res.push_back(matrix[t][j]);
}
if (++t > b) {
break;
}
// 从上到下
for (int i = t; i <= b; ++i) {
res.push_back(matrix[i][r]);
}
if (--r < l) {
break;
}
// 从右往左
for (int j = r; j >= l; --j) {
res.push_back(matrix[b][j]);
}
if (--b < t) {
break;
}
// 从下往上
for (int i = b; i >= t; --i) {
res.push_back(matrix[i][l]);
}
if (++l > r) {
break;
}
}
return res;
}
};
Go
func spiralOrder(matrix [][]int) []int {
if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 {
return []int{}
}
l, r, t, b := 0, len(matrix[0])-1, 0, len(matrix)-1
res := make([]int, (r+1)*(b+1))
k := 0
for {
// 从左到右
for i, j := t, l; j <= r; j++ {
res[k] = matrix[i][j]
k++
}
if t++; t > b {
break
}
// 从上到下
for i, j := t, r; i <= b; i++ {
res[k] = matrix[i][j]
k++
}
if r--; l > r {
break
}
// 从右到左
for i, j := b, r; j >= l; j-- {
res[k] = matrix[i][j]
k++
}
if b--; t > b {
break
}
// 从下到上
for i, j := b, l; i >= t; i-- {
res[k] = matrix[i][j]
k++
}
if l++; l > r {
break
}
}
return res
}
JS
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return [];
}
let l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1;
let res = new Array((r+1) * (b+1));
let k = 0;
while (true) {
// 从左到右
for (let i = t, j = l; j <= r; j++) {
res[k++] = matrix[i][j];
}
if (++t > b) break;
// 从下往上
for (let i = t, j = r; i <= b; i++) {
res[k++] = matrix[i][j];
}
if (l > --r) break;
// 从右往左
for (let i = b, j = r; j >= l; j--) {
res[k++] = matrix[i][j];
}
if (t > --b) break;
// 从下往上
for (let i = b, j = l; i >= t; i--) {
res[k++] = matrix[i][j];
}
if (++l > r) break;
}
return res;
};