螺旋矩阵

题目描述

给你一个 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]

思路&js代码

1、标记数组

var spiralOrder = function (matrix) {
  if (!matrix.length || !matrix[0].length) return []
 
  const m = matrix.length // 行数
  const n = matrix[0].length // 列数
  const all = m * n // 所有的长度
  const result = new Array(all) // 结果集
 
  // 标记已经访问过的
  const visitied = new Array(m).fill(0).map(item => new Array(n).fill(false))
 
  let posRow = 0 // 当前的行
  let posCol = 0 // 当前的列
	const directionEnum = {
		toRight: 'toRight',
		toBottom: 'toBottom',
		toLeft: 'toLeft',
		toTop: 'toTop'
	}
  let direction = directionEnum.toRight
 
  for (let i = 0; i < all; i++) {
    result[i] = matrix[posRow][posCol]
    visitied[posRow][posCol] = true
 
    // 找下一个位置
    if (direction === directionEnum.toRight) {
      if (visitied[posRow][posCol + 1] === false) {
        posCol++
      } else {
        direction = directionEnum.toBottom
        posRow++
      }
			continue
    }
 
    if (direction === directionEnum.toBottom) {
      if (visitied[posRow + 1]?.[posCol] === false) {
        posRow++
      } else {
        direction = directionEnum.toLeft
        posCol--
      }
			continue
    }
 
    if (direction === directionEnum.toLeft) {
      if (visitied[posRow][posCol - 1] === false) {
        posCol--
      } else {
        direction = directionEnum.toTop
        posRow--
      }
			continue
    }
 
    if (direction === directionEnum.toTop) {
      if (visitied[posRow - 1]?.[posCol] === false) {
        posRow--
      } else {
        direction = directionEnum.toRight
        posCol++
      }
			continue
    }
  }
 
	console.log(result)
 
  return result
}
 
spiralOrder([
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
])

2、四指针

var spiralOrder = function (matrix) {
  if (!matrix.length || !matrix[0].length) return []
  const m = matrix.length
  const n = matrix[0].length
 
  let L = 0,
    R = n - 1,
    T = 0,
    B = m - 1
 
  let i = -1,
    j = 0
 
  const res = new Array()
  while (L <= R && T <= B) {
    while (++i <= R) res.push(matrix[j][i])
    T++
    i--
 
    while (++j <= B) res.push(matrix[j][i])
    R--
    j--
 
    while (--i >= L && res.length < m * n) res.push(matrix[j][i])
    B--
    i++
 
    while (--j >= T && res.length < m * n) res.push(matrix[j][i])
    L++
    j++
  }
  console.log(res)
  return res
}