您现在的位置是:网站首页> 内容页

使用 JS 输出螺旋矩阵

  • 809海立方登录注册
  • 2019-06-14
  • 260人已阅读
简介关于螺旋矩阵这是我曾经遇到过的面试题,在LeetCode上找到了题目的原型,难度中等。题目描述如下:给定一个包含mxn个元素的矩阵(m行n列),请按照顺时针螺旋顺序,

关于螺旋矩阵

这是我曾经遇到过的面试题,在 LeetCode 上找到了题目的原型,难度中等。题目描述如下:

给定一个包含 m x n 个元素的矩阵(m 行 n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

输入:[ [ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ]]输出: [123698745]

示例 2:

输入:[ [1 2 3 4] [5 6 7 8] [9101112]]输出: [123481211109567]

解题思路

[[1 1 1 1 1 1 1] [1 2 2 2 2 2 1] [1 2 3 3 3 2 1] [1 2 2 2 2 2 1] [1 1 1 1 1 1 1]]

这是一道难度中等的题目,但是第一次看到题目时还是有一些困惑,不过仔细分析后很容易找到思路。比较直观的思路是逐层法,从外向内循环每一层。其中单层循环的方法也有很多,我使用了插入法循环每一层。以下是 4X4 矩阵循环的步骤:

/** * -------------------------------------------- * 以 4X4 矩阵为例 * * [[ 1 2 3 4] * [ 5 6 7 8] * [ 9101112] * [13141516]] * * -------------------------------------------- * 循环第一层 * * [[ 1 2 3 4] | * [ 5 8] | * [ 9 12] | * [13141516]] ▼ * * -------------------------------------------- * 将元素按顺序插入数组,`|` 表示插入位置 * * [ 1 2 3 4 |] * (8 5)┘ * * [ 1 2 3 4 8 | 5] * (12 9)┘ * * [ 1 2 3 4 8 12 | 9 5] * (16 15 14 13)┘ * * [ 1 2 3 4 8 12 16 15 14 13 9 5] * * 第一层循环结束 * */

通过以上步骤拆分,可以看到输出螺旋矩阵还是比较容易的,以下是具体的 JS 代码。

/** * @param {number[][]} matrix * @return {number[]} */var spiralOrder = function(matrix) { // 最终返回的结果数组 var ans = [] var spiralLoop = function() { // 临时数组 var arr = [] for (var i = 0 i < matrix.length i++) { if (i === 0) { arr = arr.concat(matrix[0]) } if (i > 0 && i < matrix.length - 1) { var insertRight = matrix[0].length === 1 ? [] : arr.splice(-(i - 1) i - 1) // 插入位置右侧的元素 last = matrix[i].splice(-1 1) // 中间行尾元素 first = matrix[i].splice(0 1) // 中间行首元素 // 在指定位置插入元素 arr = arr.concat(last first insertRight) } if (matrix.length > 1 && i === matrix.length - 1) { var insertRight = matrix[0].length === 1 ? [] : arr.splice(-(matrix.length - 2) matrix.length - 2) // 将最后一行倒叙排列然后插入指定位置 arr = arr.concat(matrix[matrix.length - 1].reverse() insertRight) } } // 删除矩阵的首尾行,得到的就是下一次需要遍历的矩阵 matrix.splice(0 1) matrix.splice(-1 1) ans = ans.concat(arr) // 根据矩阵内是否还存在数组进行递归 if (matrix.length >= 1) { spiralLoop(matrix) } } spiralLoop(matrix) return ans}

以上程序的运行时间大约在 60 ms 左右,超过所有提交答案的五成,中规中矩吧,距离最优算法还有一定差距。

官方答案

LeetCode 原站给出了这道题的解题思路及代码,中文站则没有。官方介绍了两种方法,一种是模拟法,另一种是逐层法,其中逐层法的思路和我的思路是相同的,不过单层循环的方法不同。对于二维矩阵的题目,我最先想到的也是模拟法,也就是模拟行走路线及方向,但是因为判断条件有点复杂而放弃了。具体实现可以看官网文章 https://leetcode.com/articles/spiral-matrix/,以下是两种方法的 python 实现,因时间关系,我就不写 JS 版本了,后续有时间再补上,感兴趣的博友可以自己转换。

1、模拟法

class Solution(object): def spiralOrder(self matrix): if not matrix: return [] R C = len(matrix) len(matrix[0]) seen = [[False] * C for _ in matrix] ans = [] dr = [0 1 0 -1] dc = [1 0 -1 0] r = c = di = 0 for _ in range(R * C): ans.append(matrix[r][c]) seen[r][c] = True cr cc = r + dr[di] c + dc[di] if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]: r c = cr cc else: di = (di + 1) % 4 r c = r + dr[di] c + dc[di] return ans

2、逐层法

class Solution(object): def spiralOrder(self matrix): def spiral_coords(r1 c1 r2 c2): for c in range(c1 c2 + 1): yield r1 c for r in range(r1 + 1 r2 + 1): yield r c2 if r1 < r2 and c1 < c2: for c in range(c2 - 1 c1 -1): yield r2 c for r in range(r2 r1 -1): yield r c1 if not matrix: return [] ans = [] r1 r2 = 0 len(matrix) - 1 c1 c2 = 0 len(matrix[0]) - 1 while r1 <= r2 and c1 <= c2: for r c in spiral_coords(r1 c1 r2 c2): ans.append(matrix[r][c]) r1 += 1 r2 -= 1 c1 += 1 c2 -= 1 return ans

文章评论

Top