Spiral Matrix

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

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

Solution 1

把遍历过的排除，即每次走完一行或一列，边界缩小。用rowBegin代表遍历起始行, rowEnd代表终点行, colBegin代表起始列, colEnd终点列。每遍历了一行, 就将相应begin和end指针往尚未遍历的方向移动。

Code

/*
 * @lc app=leetcode id=54 lang=cpp
 *
 * [54] Spiral Matrix
 */
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        vector<int> res;
        int row_begin = 0, row_end = M - 1, col_begin = 0, col_end = N - 1;
        while (row_begin <= row_end && col_begin <= col_end) {
            for (int i = col_begin; i <= col_end; ++i) res.push_back(matrix[row_begin][i]);
            ++row_begin;
            for (int i = row_begin; i <= row_end; ++i) res.push_back(matrix[i][col_end]);
            --col_end;
            if (row_begin > row_end) break;
            for (int i = col_end; i >= col_begin; --i) res.push_back(matrix[row_end][i]);
            --row_end;
            if (col_begin > col_end) break;
            for (int i = row_end; i >= row_begin; --i) res.push_back(matrix[i][col_begin]);
            ++col_begin;
        }
        return res;
    }
};

Analysis

时间复杂度O(MN).

Solution 2

模拟走格的过程。当下一步会走出边界或重新走到已经访问过的时，变换方向。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        const auto R = matrix.size();
        if (R == 0) {
            return res;
        }
        const auto C = matrix[0].size();
        int dirs[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<bool>> seen(R, vector<bool>(C, false)); 
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < R * C; ++i) {
            res.push_back(matrix[r][c]);
            seen[r][c] = true;
            int rc = r + dirs[di][0];
            int cc = c + dirs[di][1];
            if (rc >= 0 && rc < R && cc >= 0 && cc < C && !seen[rc][cc]) {
                r = rc;
                c = cc;
            } else {
                di = (di + 1) % 4;
                r += dirs[di][0];
                c += dirs[di][1];
            }
        }

        return res;
    }
};