54.Spiral-Matrix

54. Spiral Matrix

题目地址

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

题目描述

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

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

代码

Approach 1: Simulation

Complexity Analysis

• Time Complexity: O(_N), where N_ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

• Space Complexity: O_(_N), the information stored in seen and in ans.

class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0) return ans;
    int R = matrix.length;
    int C = matrix[0].length;

    boolean[][] seen = new boolean[R][C];
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0}; // top, right, bottom, left
         int r = 0, c = 0, di = 0;
    for (int i = 0; i < R * C; i++) {
      ans.add(matrix[r][c]);
      seen[r][c] = true;
      int cr = r + dr[di];
      int cc = c + dc[di];
      if (cr >= 0 && cr < R && cc >= 0 && cc < C && !seen[cr][cc]) {
        r = cr;
        c = cc;
      } else {
        di = (di + 1) % 4;
        r += dr[di];
        c += dc[di];
      }
    }

    return ans;
  }
}

Approach 2: Layer-by-Layer

class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List ans = new ArrayList();
    if (matrix.length == 0) return ans;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix.length[0] - 1;
    while (r1 <= r2 && c1 <= c2) {
      // top
      for (int c = c1; c <= c2; c++) {
        ans.add(matrix[r1][c]);
      }
      // right
      for (int r = r1 + 1; r <= r2; r++) {
        ans.add(matrix[r][c2]);
      }

      if (r1 < r2 && c1 < c2) { // 奇数最后一轮无法进行
        // bottom
        for (int c = c2 - 1; c > c1; c--) {
          ans.add(matrix[r2][c]);
        }
        // left
        for (int r = r2; r < r1; r--) {
          ans.add(matrix[r][c1]);
        }
      }

      r1++;
      r2--;
      c1++;
      c2--;
    }

    return ans;
  }
}