【牛客-算法】NC38 螺旋矩阵

简介: 【牛客-算法】NC38 螺旋矩阵

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.运行结果


image.png

成功通过!


相关文章
|
4天前
|
存储 机器学习/深度学习 算法
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵
【算法训练-数组 三】【数组矩阵】螺旋矩阵、旋转图像、搜索二维矩阵
37 0
|
4天前
|
算法
|
6月前
|
算法
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
40 0
|
6月前
|
算法 索引
代码随想录算法训练营第二天 |977.有序数组平方,209.长度最小的字数组,59.螺旋矩阵
代码随想录算法训练营第二天 |977.有序数组平方,209.长度最小的字数组,59.螺旋矩阵
|
9月前
|
算法 索引
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
|
11月前
|
人工智能 算法
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
【数据结构与算法】数组2:双指针法 & 二分法(螺旋矩阵)
68 0
|
算法 Java
【算法】给你一个数字算出螺旋矩阵,要不要来试一试?
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的
66 2
【算法】给你一个数字算出螺旋矩阵,要不要来试一试?
|
算法
【Day19】LeetCode算法刷题(附带解题思路、代码注释详细) 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】
学习了解附带解题思路、代码注释详细) 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】。
89 0
【Day19】LeetCode算法刷题(附带解题思路、代码注释详细) 【777. 在LR字符串中交换相邻字符】 【54. 螺旋矩阵】
|
算法 Oracle 关系型数据库
LeetCode(算法)- 54. 螺旋矩阵
LeetCode(算法)- 54. 螺旋矩阵
110 0
☆打卡算法☆LeetCode 59、螺旋矩阵 II 算法解析
“给定一个正整数,按顺时针顺序螺旋排列生成矩阵。”