Spiral Matrix (M)

題目

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]

題意

將給定矩陣中的元素按照從外圈到內圈，順時針螺旋輸出，

思路

直接模擬從外到內的順時針路徑，輸出每一個路徑上的元素，從左上角頂點開始，初始方向向右，每次按照指定方向前進一個元素，如果下一個元素在矩陣外或已經在之前被訪問過，則將前進方向順時針轉90°，重復上述操作，直到最后一次到達的位置在矩陣外或已經被訪問過，

官方解答中還介紹了一種層遍歷的方法：

{{uploading-image-675813.png(uploading...)}}
如圖，每次遍歷一層，將當前層中元素按照紅色行從左到右、綠色列從上到下、藍色行從右到左、紫色列從下到上的順序添加到結果集中，完成后將上下左右四個邊界各向內推進一層，重復操作，

代碼實作

Java

模擬

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        // 空矩陣處理
        if (matrix.length == 0) {
            return ans;
        }

        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];	// 記錄已訪問過元素
        int[] iPlus = {0, 1, 0, -1};
        int[] jPlus = {1, 0, -1, 0};
        int direction = 0;							// 下一次前進方向,0123分別為右下左上
        int i = 0, j = 0;							// 當前位置

        for (int count = 0; count < m * n; count++) {
            ans.add(matrix[i][j]);
            visited[i][j] = true;

            // 先判斷以當前方向走到的下一個位置是否合法，不合法則轉向
            int nextI = i + iPlus[direction];
            int nextJ = j + jPlus[direction];
            if (nextI == -1 || nextJ == -1 || nextI == m || nextJ == n || visited[nextI][nextJ]) {
                direction = (direction + 1) % 4;
                i += iPlus[direction];
                j += jPlus[direction];
            } else {
                i = nextI;
                j = nextJ;
            }
        }

        return ans;
    }
}

層遍歷

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

        int m = matrix.length, n = matrix[0].length;

        // 四個引數確定四個邊
        int rowUp = 0, rowDown = m - 1;
        int colLeft = 0, colRight = n - 1;

        while (rowUp <= rowDown && colLeft <= colRight) {
            for (int c = colLeft; c <= colRight; c++) {
                ans.add(matrix[rowUp][c]);
            }
            for (int r = rowUp + 1; r <= rowDown; r++) {
                ans.add(matrix[r][colRight]);
            }
			
            // 只有當前層不是一直線時，才有下邊和左邊
            if (rowUp < rowDown && colLeft < colRight) {
                for (int c = colRight - 1; c >= colLeft + 1; c--) {
                    ans.add(matrix[rowDown][c]);
                }
                for (int r = rowDown; r >= rowUp + 1; r--) {
                    ans.add(matrix[r][colLeft]);
                }
            }

            // 向內縮小
            rowUp++;
            rowDown--;
            colLeft++;
            colRight--;
        }

        return ans;
    }
}

JavaScript

模擬

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  if (matrix.length === 0) {
    return []
  }

  let order = []
  let m = matrix.length
  let n = matrix[0].length

  let stepI = [0, 1, 0, -1]
  let stepJ = [1, 0, -1, 0]
  let dir = 0
  let visited = new Array(m).fill(0).map(v => new Array(n).fill(false))
  let i = 0, j = 0

  for (let cnt = 0; cnt < m * n; cnt++) {
    order.push(matrix[i][j])
    visited[i][j] = true

    let nextI = i + stepI[dir]
    let nextJ = j + stepJ[dir]
    if (nextI === m || nextJ === n || nextJ === -1 || visited[nextI][nextJ]) {
      dir = (dir + 1) % 4
      nextI = i + stepI[dir]
      nextJ = j + stepJ[dir]
    }
    i = nextI
    j = nextJ
  }

  return order
}

層遍歷

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  if (matrix.length === 0) {
    return []
  }

  let order = []
  let m = matrix.length
  let n = matrix[0].length

  let left = 0
  let right = n - 1
  let top = 0
  let bottom = m - 1

  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) {
      order.push(matrix[top][i])
    }
    for (let i = top + 1; i <= bottom; i++) {
      order.push(matrix[i][right])
    }
    if (top < bottom && left < right) {
      for (let i = right - 1; i > left; i--) {
        order.push(matrix[bottom][i])
      }
      for (let i = bottom; i > top; i--) {
        order.push(matrix[i][left])
      }
    }
    top++
    bottom--
    left++
    right--
  }

  return order
}

標籤：其他

上一篇：0053. Maximum Subarray (E)

下一篇：資料結構之特殊矩陣