| 算法：二维矩阵螺旋遍历 | 您所在的位置：网站首页 › 手机为什么安装不了拼多多 › 算法：二维矩阵螺旋遍历 |
算法：二维矩阵螺旋遍历
|
54. 螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]示例 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]提示： m == matrix.lengthn == matrix[i].length1 res.push(matrix[i][j]); count ++; matrix[i][j] = READED;// 已读 const next = [i + DIRECTIONS[pointer][0], j + DIRECTIONS[pointer][1]];// 按照当前方向尝试走下一步 // 如果下一步到了边界，或者之前已读过的位置，则调整方向 if (matrix[next[0]] === undefined || matrix[next[0]][next[1]] === READED || matrix[next[0]][next[1]] === undefined) { pointer = (pointer +1) % 4;// 改变方向 } i += DIRECTIONS[pointer][0]; j += DIRECTIONS[pointer][1]; } return res } // 测试： spiralOrder([ [1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20], ]) 解法2：按层遍历我们将二位矩阵想象成一个洋葱切面 其实很简单，对角线上的两个点就能确定这层皮的框框，记录左上角[top,left],右上角[bottom,right] 一层层扒下去，直到top === bottom或者left === right结束
代码 /** * 思路 * 1.像剥洋葱似的一层层扒皮 * 2.通过对角线的两个点确定每层皮四个点 * @param matrix */ const spiralOrder1 = (matrix: number[][]): number[] => { const res: number[] = []; // 根据对角线就可以确定矩阵的四个边 let top = 0, left = 0, bottom = matrix.length-1, right = matrix[0].length-1; // 扒皮 while(top res.push(matrix[top][l]) } // 上 -> 下（右边） for (let i = top; i res.push(matrix[bottom][i]) } // 下 -> 上（左边） for (let i = bottom; i > top; i--) { res.push(matrix[i][left]) } // 往里进一层 top ++; left ++; bottom --; right -- } return res; } // 测试： spiralOrder1([ [1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20], ]) spiralOrder1([ [1,2,], [6,7,], [11,12,], [16,17,], ]) 复杂度对比矩阵元素个数为n,返回值不计入复杂度 解法1 时间复杂度：O(n)空间复杂度：O(1)解法2 虽然里面有4个for循环，但是不会出现重复遍历的元素，因此时间复杂度是元素的数量 时间复杂度：O(n)空间复杂度：O(1)两个相比较，我感觉解法2更好一些，使用的变量少 思路扩展先增加一个100x100的二位矩阵的测试用例 思考一个问题，矩阵数据特别大，无法一次性加载到内存中，应该如何进行螺旋遍历呢？ 欢迎提出解答方案 |
每扒掉一层皮，矩阵就小一层，。不过洋葱是圆的，我们的矩阵是方形的，因此要确定没层皮的四个角上的点。
【本文地址】
公司简介
联系我们