This is the 12th day of my participation in the August More Text Challenge. For details, see: August More Text Challenge

preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

Given a matrix with m rows and N columns, return all the elements of the matrix in a clockwise spiral order.

Example 1:



Input: matrix = [[1,2,3],[4,5,6],[7,8,9]

Output:,2,3,6,9,8,7,4,5 [1]

Example 2:



Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]

Output:,2,3,4,8,12,11,10,9,5,6,7 [1]

Link: leetcode-cn.com/problems/sp…

Answer key

The problem is how to walk the matrix clockwise. Usually this spiral traversal problem, the main points are as follows.

  1. Define an array of directions. For this problem, there are four directions, from left to right [0, 1], from top to bottom [1, 0], from right to left [0, -1], and from bottom to top [-1, 0]. These directions indicate that x and y change with each move.

  2. Define boundaries. Initialize the upper and left boundaries to 0, and the right and lower boundaries to n-1, respectively.

  3. Update direction and boundary size. When walking forward, each time you reach a boundary, change direction and minimize the corresponding boundary. For example, when you go to the last element of the first row, change the direction to [1, 0] and change the upper boundary from 1 to 0. The direction we’re traversing is represented by a variable I, which is in the range 0 to 3, which is the size of the direction array.

Taking the above three steps together, we can understand the following code.

O(mn) in time, O(1) in space

/ * * *@param {number[][]} matrix
 * @return {number[]}* /
var spiralOrder = function(matrix) {
    let res = []
    let m = matrix.length
    let n = matrix[0].length
    // Define four boundaries
    let left = up = 0
    let right = n - 1
    let bottom = m - 1
    // Traverse the starting point
    let x = 0
    let y = 0
    // Direction array
    const dir = [[0.1], [1.0], [0, -1], [...1.0]]
    // The variable that determines the direction
    let i = 0
    
    while (res.length < m * n) {
      res.push(matrix[x][y])
      // The right boundary is reached
      if (i === 0 && y === right) {
        ++up
        ++i
        // Reaches the lower boundary
      } else if (i === 1 && x === bottom) {
        --right
        ++i
        // The left boundary is reached
      } else if (i === 2 && y === left) {
        --bottom
        ++i
        // The upper boundary is reached
      } else if (i === 3 && x === up) {
        ++left
        ++i
      }
      // Update the direction
      i %= 4
      // Iterates forward
      x += dir[i][0]
      y += dir[i][1]}return res
};
Copy the code