🔥 该专栏作为算法题笔记，记录算法的思路、遇到的问题，以及能跑的代码，持续更新中！
推荐一款面试、刷题神器牛客网：👉开始刷题学习👈
1.题目描述
描述
给定一个
m
∗
n
m * n
m∗n 大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
数据范围：
0
≤
n
,
m
≤
10
0≤n,m≤10
0≤n,m≤10，矩阵中任意元素都满足
∣
v
a
l
∣
≤
100
∣val∣≤100
∣val∣≤100
要求：空间复杂度
O
(
n
m
)
O
(
n
m
)
O(nm)O(nm)
O(nm)O(nm) ，时间复杂度
O
(
n
m
)
O
(
n
m
)
O(nm)O(nm)
O(nm)O(nm)
示例
输入：
[[1,2,3],[4,5,6],[7,8,9]]
返回值：
[1,2,3,6,9,8,7,4,5]
2.算法设计思路
螺旋矩阵是一个很经典的题了。
这其实就是一个二维数组的遍历，但我们需要按照一直特殊的方式——螺旋来进行遍历。
简述遍历过程
- 从起点
(
0
,
0
)
(0,0)
(0,0)开始，先一直往右走
- 碰到边界或已经走过的格子就拐弯，顺时针拐
9
0
o
90^o
90o
- 不断重复直行和拐弯，直到走过所有的格子
3.算法实现
注：这里并不是完整代码，而只是核心代码的模式
C++实现代码
/**
*
* @param matrix int整型二维数组
* @param matrixRowLen int matrix数组行数
* @param matrixColLen int* matrix数组列数
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/
//疑惑：为什么数组的列数参数要用(int*)类型？
int* spiralOrder(int** matrix, int matrixRowLen, int* matrixColLen, int* returnSize )
{
// write code here
*returnSize = matrixRowLen * (*matrixColLen);
int* a = (int*)malloc(*returnSize * sizeof(int));//要返回的数组
int BIG = 1234567890;//用以标志走过的地方
for(int i = 0, j = 0, it_i = 0, it_j = 1, n = 0, direction = 0; n < *returnSize; n++)
{
a[n] = matrix[i][j];
matrix[i][j] = BIG;
//该拐弯了吗？(碰到边界或已经走过的格子)
if(i+it_i >= matrixRowLen || j+it_j >= *matrixColLen || i+it_i < 0 || j+it_j < 0 || matrix[i+it_i][j+it_j] == BIG)
{
direction = (direction + 1) % 4;
switch(direction){
case 0:
it_i = 0; it_j = 1; break;//右
case 1:
it_i = 1; it_j = 0; break;//下
case 2:
it_i = 0; it_j = -1; break;//左
case 3:
it_i = -1; it_j = 0; break;//上
default:
printf("error:direction\n");
}
}
i += it_i;
j += it_j;
}
return a;
}
遇到问题 1：关于函数的(int*)类型参数
在我印象中，int*类型的参数是用来传一维数组的，这里用来传数组的列数，我就有些蒙圈了。
后面看到returnSize也是int*类型的，我就认识到它是用来传引用的。其实传数组的时候，这个int*参数也仅仅是接收一个地址而已，并不包含数组大小的信息，是一样的。甚至于，在函数中插入下面这样的代码，也仍然可以正常运行：
returnSize[1] = 9;
printf("%d", returnSize[1]);
我平时习惯上传引用都是使用int & returnSize这样的写法，然而我在牛客的C语言模式这样写就会报错，可能是我C语言和C++是混着学的？
遇到问题2：关于malloc函数用法
关于动态分配语句int* a = (int*)malloc(*returnSize * sizeof(int));，我原来是写的int* a = (int*)malloc(*returnSize);，结果发生了段错误（内存非法访问）。
后面仔细查了才发现，后面分配内存的大小是用字节数来表示的，而不是传给它元素的个数（基础没打牢，代码很难跑啊）。
这里牛客有一个缺点（不知道是不是bug），发生了段错误的时候，我想使用printf()来定位错误的位置，结果它根本就什么都没有打印出来，即使我是在函数开头写的一句printf("hello, world!")。
4.运行结果
成功通过！
今天的分享就到这里啦，快来一起刷题叭！
👉开始刷题学习👈
感谢阅读！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114797.html
