剑指 Offer 29. 顺时针打印矩阵(三十七)

一、题目描述

这是 LeetCode 上:剑指 Offer 29. 顺时针打印矩阵,难度为 简单

Tag:「数组」、「矩阵」、「模拟」

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

1
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]

提示:

1、0 <= matrix.length <= 100

2、0 <= matrix[i].length <= 100

二、解题思路

可以将矩阵看成若干层,首先打印最外层的元素,其次打印次外层的元素,直到打印最内层的元素。

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,剩下的元素都是第 3 层。

1
2
3
4
5
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]

对于每层,从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left),右下角位于 (bottom,right),按照如下顺序遍历当前层的元素。

1、从左到右遍历上侧元素,依次为 (top,left) 到 (top,right)。

2、从上到下遍历右侧元素,依次为 (top+1,right) 到 (bottom,right)。

3、如果 left<right 且 top<bottom,则从右到左遍历下侧元素,依次为 (bottom,right−1) 到 (bottom,left+1),以及从下到上遍历左侧元素,依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后,将 left 和 top 分别增加 1,将 right 和 bottom 分别减少 1,进入下一层继续遍历,直到遍历完所有元素为止。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int rows = matrix.length, columns = matrix[0].length;
int[] order = new int[rows * columns];
int index = 0;
int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
while (left <= right && top <= bottom) {
for (int column = left; column <= right; column++) {
order[index++] = matrix[top][column];
}
for (int row = top + 1; row <= bottom; row++) {
order[index++] = matrix[row][right];
}
if (left < right && top < bottom) {
for (int column = right - 1; column > left; column--) {
order[index++] = matrix[bottom][column];
}
for (int row = bottom; row > top; row--) {
order[index++] = matrix[row][left];
}
}
left++;
right--;
top++;
bottom--;
}
return order;
}
}

复杂度分析

1、时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

2、空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。

三、总结

本道算法题难度为简单,设计好从外到里的一个打印思路并能快速求解。

好了,本篇文章到这里就结束了,感谢你的阅读🤝


剑指 Offer 29. 顺时针打印矩阵(三十七)
https://sweetying520.github.io/2022/09/10/A37-剑指 Offer 29. 顺时针打印矩阵(三十七)/
作者
sweetying
发布于
2022年9月10日
许可协议