54. Spiral Matrix

Leetcode

https://leetcode.com/problems/spiral-matrix/

題目

Given an m x n matrix, return all elements of the matrix in spiral order.

解答

• 方法一

每次都加入第一列，然後逆時針旋轉矩陣 90 度，再依次加入第一列

var spiralOrder = function(matrix) {
    var rotate = function(matrix) {
      const m = matrix.length;
      const n = matrix[0].length;
      const result = Array.from({length: n}, () => []);
      for(let i=0; i<m; i++) {
        for(let j=0; j<n; j++) {
          result[j].push(matrix[i][n-j-1]);
        }
      }

      return result
    }; 

    const result = [];
    while(matrix.length) {
      const next = matrix.splice(0, 1)[0];
      result.push(...next);
      if (matrix.length) {
        matrix = rotate(matrix);
      }
    }

    return result;
};

Runtime: 68 ms, faster than 88.47% of JavaScript online submissions for Spiral Matrix.

Memory Usage: 38.6 MB, less than 37.64% of JavaScript online submissions for Spiral Matrix.

• 方法二

設定四個方向(往右 -> 往下 -> 往左 -> 往上)，依序遍歷

var spiralOrder = function(matrix) {
  let startRow = 0;
  let startCol = 0;
  let endRow = matrix.length - 1;
  let endCol = matrix[0].length - 1;

  const result = [];
  while(true) {
    for(let i=startCol; i<=endCol; i++) {
      result.push(matrix[startRow][i]);
    }
    if(++startRow > endRow) break;

    for(let i=startRow; i<=endRow; i++) {
      result.push(matrix[i][endCol]);
    }
    if(startCol > --endCol) break;

    for(let i=endCol; i>=startCol; i--) {
      result.push(matrix[endRow][i]);
    }
    if(startRow > --endRow) break;

    for(let i=endRow; i>=startRow; i--) {
      result.push(matrix[i][startCol]);
    }
    if(++startCol > endCol) break;
  }

  return result;
};

Runtime: 68 ms, faster than 88.31% of JavaScript online submissions for Spiral Matrix.

Memory Usage: 38.9 MB, less than 18.59% of JavaScript online submissions for Spiral Matrix.

https://www.youtube.com/watch?v=HnP-pJLFZwY

測資

let matrix = [[1,2,3],[4,5,6],[7,8,9]]
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

console.log(spiralOrder(matrix));

參考資料

• https://www.youtube.com/watch?v=HnP-pJLFZwY