给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
https://leetcode-cn.com/problems/spiral-matrix/
示例1：
image输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例2：
image输入：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]
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Java解法
思路：
- 顺时针输出，由外向内，起点都是左上角
- 考虑记录圈数，记录每圈输出规则
- 这里要注意当圈为一横 或一竖的情况（需要计算好边界，注意重复与遗漏）
package sj.shimmer.algorithm.m2;
import java.util.ArrayList;
import java.util.List;
/**
* Created by SJ on 2021/2/25.
*/
class D32 {
public static void main(String[] args) {
System.out.println(spiralOrder(new int[][]{{2},{3}}));
System.out.println(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9},}));
System.out.println(spiralOrder(new int[][]{{1,2,3,4},{5,6,7,8},{9,10,11,12}}));
}
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if (matrix != null) {
int height = matrix.length;
int width = matrix[0].length;
int maxTurn = (Math.min(height, width)+1) / 2;
for (int i = 0; i < maxTurn; i++) {
int top = i;
while (top < width - i) {
list.add(matrix[i][top]);
top++;
}
int right = i+1;
while (right < height - i-1) {
list.add(matrix[right][width-i-1]);
right++;
}
if (i==height-1-i) {
continue;
}
int bottom = width-i-1;
while (bottom >= i) {
list.add(matrix[height-i-1][bottom]);
bottom--;
}
if (i==width-i-1) {
continue;
}
int left = height-i-2;
while (left > i) {
list.add(matrix[left][i]);
left--;
}
}
}
return list;
}
}
image
官方解
https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
-
模拟
使用辅助矩阵来模拟路径，不是特别有想法的解法
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
-
按层模拟
差不多的思路，但解法有一些区别
class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> order = new ArrayList<Integer>(); if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return order; } int rows = matrix.length, columns = matrix[0].length; int left = 0, right = columns - 1, top = 0, bottom = rows - 1; while (left <= right && top <= bottom) { for (int column = left; column <= right; column++) { order.add(matrix[top][column]); } for (int row = top + 1; row <= bottom; row++) { order.add(matrix[row][right]); } if (left < right && top < bottom) { for (int column = right - 1; column > left; column--) { order.add(matrix[bottom][column]); } for (int row = bottom; row > top; row--) { order.add(matrix[row][left]); } } left++; right--; top++; bottom--; } return order; } }- 时间复杂度：O(mn)
- 空间复杂度：O(1)
