#P4014. 螺旋矩阵
-
ID: 2221
Tried: 142
Accepted: 55
Difficulty: 3
螺旋矩阵
题目内容
给你一个 m 行 n 列的矩阵 matrix，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
输入描述
第一行两个整数m，n 接下来m行，每行n列，代表矩阵matrix。 每行的数字之间以空格分隔。
输出描述
输出一行，按题目要求顺序输出每个数字，数字之间以空格分隔。
样例1
输入
3 3
1 2 3
4 5 6
7 8 9
输出
1 2 3 6 9 8 7 4 5
样例2
输入
3 4
1 2 3 4
5 6 7 8
9 10 11 12
输出
1 2 3 4 8 12 11 10 9 5 6 7
提示
- m==matrix.lengt
- n==matrix[i].length
- 1<=m,n<=10
- −100<=matrix[i][j]<=100
螺旋矩阵遍历
题解思路
这道题的核心是模拟螺旋遍历矩阵的过程。遍历方式如下：
- 从左到右遍历上边界
- 从上到下遍历右边界
- 从右到左遍历下边界（如果仍然存在）
- 从下到上遍历左边界（如果仍然存在）
然后不断缩小边界范围，直到遍历完整个矩阵。
算法设计
我们可以定义四个变量来表示边界：
top表示上边界bottom表示下边界left表示左边界right表示右边界
遍历过程中按照顺时针方向进行：
- 遍历
top行，从left到right，然后top++ - 遍历
right列，从top到bottom，然后right-- - 如果仍然有
bottom行，则从right到left遍历该行，bottom-- - 如果仍然有
left列，则从bottom到top遍历该列，left++
不断重复上述过程，直到所有元素都被访问。
复杂度分析
由于我们遍历矩阵的每个元素一次，时间复杂度为 O(m * n)，其中 m 为行数，n 为列数。
额外使用了一个结果数组，空间复杂度为 O(1)（如果不考虑输出存储）。
代码实现
Python 代码
class Solution:
def spiralOrder(self, matrix):
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
result = []
# 定义边界
top, bottom = 0, m - 1
left, right = 0, n - 1
while top <= bottom and left <= right:
# 从左到右
for i in range(left, right + 1):
result.append(matrix[top][i])
top += 1 # 上边界下移
# 从上到下
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1 # 右边界左移
# 从右到左
if top <= bottom:
for i in range(right, left - 1, -1):
result.append(matrix[bottom][i])
bottom -= 1 # 下边界上移
# 从下到上
if left <= right:
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1 # 左边界右移
return result
# 读取输入
if __name__ == "__main__":
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
solution = Solution()
print(" ".join(map(str, solution.spiralOrder(matrix))))
Java 代码
import java.util.*;
public class Main {
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int m = matrix.length, n = matrix[0].length;
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// 从左到右
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++; // 上边界下移
// 从上到下
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--; // 右边界左移
// 从右到左
if (top <= bottom) {
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--; // 下边界上移
}
// 从下到上
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++; // 左边界右移
}
}
return result;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
Main main = new Main();
Solution solution = main.new Solution();
List<Integer> result = solution.spiralOrder(matrix);
for (int i = 0; i < result.size(); i++) {
if (i > 0) System.out.print(" ");
System.out.print(result.get(i));
}
}
}
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
if (matrix.empty() || matrix[0].empty()) return result;
int m = matrix.size(), n = matrix[0].size();
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// 从左到右
for (int i = left; i <= right; i++) {
result.push_back(matrix[top][i]);
}
top++; // 上边界下移
// 从上到下
for (int i = top; i <= bottom; i++) {
result.push_back(matrix[i][right]);
}
right--; // 右边界左移
// 从右到左
if (top <= bottom) {
for (int i = right; i >= left; i--) {
result.push_back(matrix[bottom][i]);
}
bottom--; // 下边界上移
}
// 从下到上
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.push_back(matrix[i][left]);
}
left++; // 左边界右移
}
}
return result;
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
Solution solution;
vector<int> result = solution.spiralOrder(matrix);
for (size_t i = 0; i < result.size(); i++) {
if (i > 0) cout << " ";
cout << result[i];
}
cout << endl;
return 0;
}