1.题目描述
描述
给定一个 m ∗ n m * nm∗n 大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
数据范围：0 ≤ n , m ≤ 10 0≤n,m≤100≤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^o90
o
不断重复直行和拐弯，直到走过所有的格子
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.运行结果
成功通过！
