LeetCode 54. 螺旋矩阵

题目描述

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

题解

模拟法

算法

• 根据题目说明，按顺时针方向遍历矩阵。

1. 设定几个变量： col, row 为当前坐标，dCol, dRow 为遍历方向，colL, colR 为横向坐标遍历范围，rowT, rowB 为纵向坐标遍历范围。
2. 从左上角 (col, row) = (0, 0) 开始，设定遍历方向为向右 (dCol, dRow) = (1, 0) ，遍历到最右 colR，因为这一行已经遍历过，所以修改纵坐标范围 rowT++ 。
3. 改变方向向下 (dCol, dRow) = (0, 1)，遍历到最下 rowB ，修改横坐标范围 colR—。
4. 改变方向向左 (dCol, dRow) = (-1, 0) ，遍历到最左 colL ，修改纵坐标范围 rowB—。
5. 改变方向向上 (dCol, dRow) = (0, 1) ，遍历到最上 rowT ，修改横坐标范围 colL++。
6. 已经遍历到 (col, row) = (1, 1) ，重复第2步，直到遍历完成。

代码

// C++
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int maxRow = (int)matrix.size();
    if (maxRow == 0) {
        return vector<int>();
    }
    int maxCol = (int)matrix[0].size();
    int col = 0, row = 0;
    int dCol = 1, dRow = 0;
    int colL = 0, colR = maxCol - 1;
    int rowT = 0, rowB = maxRow - 1;
    vector<int> ret(maxRow * maxCol, 0);
    for (auto i = 0; i < maxRow * maxCol; ++i) {
        ret[i] = matrix[row][col];
        if (dCol == 1 && dRow == 0 && col == colR) {
            dCol = 0;
            dRow = 1;
            rowT++;
        } else if (dCol == 0 && dRow == 1 && row == rowB) {
            dCol = -1;
            dRow = 0;
            colR--;
        } else if (dCol == -1 && dRow == 0 && col == colL) {
            dCol = 0;
            dRow = -1;
            rowB--;
        } else if (dCol == 0 && dRow == -1 && row == rowT) {
            dCol = 1;
            dRow = 0;
            colL++;
        }
        col += dCol;
        row += dRow;
    }
    return ret;
}