位元組跳動面試算法題——螺旋矩陣，醒醒...不能暈

題目

給定一個矩陣，請按照“順時針螺旋順序”傳回矩陣中的所有元素。

如下圖所示，按照箭頭的方向周遊矩陣。“順時針螺旋順序”傳回矩陣的所有元素：“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;
  }
}
           

總結

本題是一個周遊矩陣的問題。題目很清楚，邏輯也很簡單，編碼的時候需要仔細和耐心就可以避免出錯。看了本文後，你可以完成“逆時針螺旋順序”的代碼嗎？