力扣54. 螺旋矩阵

发布时间:2024年01月16日

模拟

  • 思路:
    • 转向表示:使用行下标和列下标变化;
      • 比如向上:行下标?- 1, 列下标,即 {-1, 0}
      • 同理向下 {1, 0}
      • {0, 1} 表示向右
      • {0, -1} 表示向左
    • 螺旋方向为:向右、向下、向左、向上,周期变化;
      • 从 4 个转向中周期选取

      • directIdx = (directIdx + 1) % 4;

    • 出现转向是 next 到达“边界”:
      • 真正的边界;
      • 已经访问过的成为了边界;
    • 预测下一个行列下标:
      • int nextRow = r + directions[directIdx][0];

      • int nextColumn = c + directions[directIdx][1];

    • 根据转向规则,更新行列下标:
      • r += directions[directIdx][0];

      • c += directions[directIdx][1];

    • 完整代码:
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int row = matrix.size();
        if (row == 0) {
            return {};
        }
        int column = matrix[0].size();
        if (column == 0) {
            return {};
        }

        std::vector<std::vector<bool>> visited(row, std::vector<bool>(column));
        int sz = row * column;
        std::vector<int> order(sz);

        int r = 0;
        int c = 0;
        int directIdx = 0;
        for (int i = 0; i < sz; ++i) {
            order[i] = matrix[r][c];
            visited[r][c] = true;
            int nextRow = r + directions[directIdx][0];
            int nextColumn = c + directions[directIdx][1];

            if (nextRow < 0 || nextRow >= row || 
                nextColumn < 0 || nextColumn >= column ||
                visited[nextRow][nextColumn]) {
                directIdx = (directIdx + 1) % 4;
            }

            r += directions[directIdx][0];
            c += directions[directIdx][1];
        }

        return order;
    }

private:
    static constexpr int directions[4][2] = {
        // right
        {0, 1},
        // down
        {1, 0},
        // left
        {0, -1},
        // up
        {-1, 0}
    };
};
  • 空间复杂度是 O(m x n),应该可以将复杂度降低到 O(1)
文章来源:https://blog.csdn.net/N_BenBird/article/details/135613654
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。