「题解」LeetCode 顺时针打印矩阵
程序员文章站
2024-03-23 20:13:34
...
分析
这道题目是按顺时针打印数组,其实就是读取的顺序与以前相比发生了变化。
那么就引出两个问题,边界问题和读取方向问题。
- 在边界问题上还是老样子,不要越界即可,主要可能越界的就是最外层;这里我准备用标记是否处理过的数组,所以还要卡标记数组的边界;
- 读取方向上,它有4个方向,我用了3个标记量来控制转向。x值为true表示横向前进,false表示纵向前进;在这两个方向上又分别有正向和反向,分别用pos_X和pos_Y表示x轴和y轴上的正反向;
- 思路上,就是对草稿纸上读一次的模拟,还是刚刚那个问题,需要转向时候通过标记量的设置转向即可;然后就继续往前。就是这两个点。题很简单,自己很菜…做了半天
代码
class Solution {
public int[] spiralOrder(int[][] matrix) {
/* 特殊情况处理 */
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
/* 结果数组长度 */
int[] res = new int[matrix.length * matrix[0].length];
/* 数组下标 */
int k = 0;
/* 二维数组下标 */
int i = 0, j = 0;
/* x,y方向最大值 */
int max_X = matrix[0].length;
int max_Y = matrix.length;
/* x,y方向选择 */
boolean x = true;
/* x,y正反方向记录值 */
boolean pos_X = true;
boolean pos_Y = true;
/* 记录是否处理的数组,默认为 false */
boolean[][] check = new boolean[matrix.length][matrix[0].length];
while(k != res.length) {
/* 赋值 */
res[k++] = matrix[i][j];
check[i][j] = true;
/* 转向操作,方向 1 -> 2 */
if (pos_X && x) {
if (j + 1 >= max_X || check[i][j + 1]) {
pos_X = false;
x = false;
}
}
/* 转向操作,方向 2 -> 3 */
if (pos_Y && !x) {
if (i + 1 >= max_Y || check[i + 1][j]) {
pos_Y = false;
x = true;
}
}
/* 转向操作,方向 3 -> 4 */
if (!pos_X && x) {
if ((j - 1 < 0) || check[i][j - 1]) {
pos_X = true;
x = false;
}
}
/* 转向操作,方向 4 -> 1 */
if (pos_X && !x) {
if ((i - 1 < 0) || check[i - 1][j]) {
pos_Y = true;
x = true;
}
}
/* 前进 */
if (x) {
j = pos_X ? j + 1 : j - 1;
} else {
i = pos_Y ? i + 1 : i - 1;
}
}
return res;
}
}
复杂度
时间:O(n)
空间:O(1)
但为什么AC后空间却用的很少呢,有点疑惑… 我想是做的人不够多吧hh
方向与轴的图
上一篇: vim配置之snippets代码块
下一篇: Mac上php环境配置