[数据结构与算法]字节跳动面试算法题——螺旋矩阵，醒醒...不能晕

题目

给定一个矩阵，请按照“顺时针螺旋顺序”返回矩阵中的所有元素。
如下图所示，按照箭头的方向遍历矩阵。“顺时针螺旋顺序”返回矩阵的所有元素：“1,2,3,6,9,8,7,4,5”

分析

按照“顺时针螺旋顺序”遍历并返回矩阵中所有数据，以下为具体步骤

1. 一路向右遍历，直到到达矩阵边界或者右面元素已经遍历过
2. 一路向下遍历，直到到达矩阵边界或者下面元素已经遍历过
3. 一路向左遍历，直到到达矩阵边界或者左面元素已经遍历过
4. 一路向上遍历，直到到达矩阵边界或者上面元素已经遍历过
5. 重复步骤1~步骤4，直到矩阵中所有元素都被遍历过

题解

public class SpiralOrderMatrix {
  public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    int r = 0,
        c = 0,
        directionIndex = 0,
        row = matrix.length,
        column = matrix[0].length,
        count = row * column;
    // 右、下、左、上 四个方向
    int[][] directions = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    while (count > 0) {
      if (r < 0 || c < 0 || r == row || c == column || matrix[r][c] == Integer.MIN_VALUE) {
        // 如果到达矩阵边界或者已经遍历过此元素，则返回前一个元素
        r -= directions[directionIndex][0];
        c -= directions[directionIndex][1];
        directionIndex = (directionIndex + 1) % 4;
      } else {
        // 遍历元素
        res.add(matrix[r][c]);
        // 标记遍历过的元素
        matrix[r][c] = Integer.MIN_VALUE;
        count--;
      }
      // 下一个元素坐标
      r += directions[directionIndex][0];
      c += directions[directionIndex][1];
    }
    return res;
  }
}

总结

本题是一个遍历矩阵的问题。题目很清楚，逻辑也很简单，编码的时候需要仔细和耐心就可以避免出错。看了本文后，你可以完成“逆时针螺旋顺序”的代码吗？