螺旋矩阵
- 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
示例 1:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
解题思路
- 1、模拟顺时针螺旋顺序遍历矩阵的过程。
- 2、使用四个变量表示当前的上下左右边界,初始化为矩阵的边界。
- 3、按照顺时针螺旋顺序遍历矩阵,依次沿着上、右、下、左四个方向遍历。
- 4、每次遍历完成一个方向后,更新对应的边界,并判断是否需要继续遍历。
java实现
public class SpiralMatrix {
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int rows = matrix.length;
int cols = matrix[0].length;
int top = 0, bottom = rows - 1, left = 0, right = cols - 1;
//保证旋转区域是合法的且不会越界。
// 如果这两个条件不满足,说明已经遍历完了所有的行或列
while (top <= bottom && left <= right) {
// 遍历上边界
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
}
top++;
// 遍历右边界
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
// 检查是否还有下边界
if (top <= bottom) {
// 遍历下边界
for (int j = right; j >= left; j--) {
result.add(matrix[bottom][j]);
}
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) {
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int[][] test = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12},
{13, 14, 15, 16}
};
List<Integer> result = spiralOrder(matrix);
System.out.println("顺时针螺旋顺序遍历结果: " + result);
List<Integer> result2 = spiralOrder(test);
System.out.println("顺时针螺旋顺序遍历结果: " + result2);
}
}
时间空间复杂度
时间复杂度:O(m * n),其中 m 和 n 分别是矩阵的行数和列数
空间复杂度:O(1),只需要使用常数级别的额外空间