特定顺序遍历二维数组

54. 螺旋矩阵

思路

每次遍历完 一行 或者 一列，修改边界，越界中断

代码

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  const ret = [];
  let endRow = matrix.length - 1, endCol = matrix[0].length - 1;
  let startRow = 0, startCol = 0;
  while(true) {
    // 往右走
    for(let col = startCol; col <= endCol; col++) ret.push(matrix[startRow][col])
    if (++startRow > endRow) break
    // 往下走
    for(let row = startRow; row <= endRow; row ++) ret.push(matrix[row][endCol])
    if (startCol > --endCol) break
    // 往左走
    for(let col = endCol; col >= startCol; col --) ret.push(matrix[endRow][col])
    if (startRow > --endRow) break
    // 往上走
    for(let row = endRow; row >= startRow; row --) ret.push(matrix[row][startCol])
    if (++startCol > endCol) break
  }
  return ret;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度 #card=math&code=O%281%29)

59. 螺旋矩阵 II

思路

和54题一样，找边界，循环滚动即可

代码

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const ret = Array(n).fill(0).map(item => Array(n));
  let endRow = n-1, endCol = n-1;
  let startRow = 0, startCol = 0;
  let start = 1;

  while(true) {
    // 往右走
    for(let col = startCol; col <= endCol; col++) ret[startRow][col] = start++
    if (++startRow > endRow) break
    // 往下走
    for(let row = startRow; row <= endRow; row ++) ret[row][endCol] = start++
    if (startCol > --endCol) break
    // 往左走
    for(let col = endCol; col >= startCol; col --) ret[endRow][col] = start++
    if (startRow > --endRow) break
    // 往上走
    for(let row = endRow; row >= startRow; row --) ret[row][startCol] = start++
    if (++startCol > endCol) break
  }
  return ret;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2%29)
空间复杂度 #card=math&code=O%28N%5E2%29)

498. 对角线遍历

思路

1、假设1个坐标为 matrix[row][col]， 在一次对角线遍历时，row+col 的值是相等的
2、当row递增时，col的递减的，反之亦然
3、在遍历完一次斜角时，要反转row，col的单调性
4、确定row和 col 的临界点

代码

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var findDiagonalOrder = function(matrix) {
  let rowLen = matrix.length, colLen = matrix[0] && matrix[0].length;
  const res = [];
  if (!rowLen || !colLen) return res;
  let flag = true;

  for(let i = 0; i < rowLen + colLen; i ++) {
    let endRow = flag ? rowLen : colLen;
    let endCol = flag ? colLen : rowLen;

    let row = (i < endRow) ? i : endRow - 1;
    let col = i - row;

    while(row >= 0 && col < endCol) {{
      res.push(flag ? matrix[row][col] : matrix[col][row]);
      row--;
      col++;
    }}
    flag = !flag;
  }
  return res;
};

复杂度分析

时间复杂度 #card=math&code=O%28row%20%2A%20col%29)
空间复杂度 #card=math&code=O%281%29)