leetcode54：螺旋矩阵

题目链接

leetcode

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序 ，返回矩阵中的所有元素。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    模拟：初始位置是矩阵的左上角，初始方向是向右。
    当路径超出界限或者进入之前访问过的位置时，顺时针旋转并且进入下一个方向。

    时间复杂度：O(mn)
        其中 m 和 n 分别是输入矩阵的行数和列数。
        矩阵中的每个元素都要被访问一次。
    空间复杂度：O(mn)
        一个大小为 m*n 的矩阵，记录每个位置是否被访问过。
*/
class Solution_0 {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m == 0 || n == 0) {
            return {};
        }

        vector<int> res(m*n);
        vector<vector<bool>> visited(m, vector<bool>(n));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0; // 起点 (x, y)
        int d = 1; // 初始方向：向右

        for (int i = 0; i < m*n; i++) {
            res[i] = matrix[x][y];
            visited[x][y] = true;
            int tx = x + dx[d], ty = y + dy[d];

            if (tx < 0 || tx >= m || ty < 0 || ty >= n || visited[tx][ty]) {
                d = (d + 1) % 4;
                tx = x + dx[d], ty = y + dy[d];
            }
            x = tx, y = ty;
        }
        
        return res;
    }
};

/*
    将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。

    对于每层，从左上方开始以顺时针的顺序遍历所有元素。
    假设当前层的左上角位于 (top, left)，右下角位于 (bottom, right)，按照如下顺序遍历当前层的元素。
        1.从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。
        2.从上到下遍历右侧元素，依次为 (top + 1, right) 到 (bottom, right)。
        3.left < right 且 top < bottom，
            从右到左遍历下侧元素，依次为 (bottom, right − 1) 到 (bottom, left + 1)，
            从下到上遍历左侧元素，依次为 (bottom, left) 到 (top + 1, left)。
    遍历完当前层的元素之后，将 left 和 top 分别加 1，将 right 和 bottom 分别减 1，
    进入下一层继续遍历，直到遍历完所有元素为止。

    时间复杂度：O(mn)
        其中 m 和 n 分别是输入矩阵的行数和列数。
        矩阵中的每个元素都要被访问一次。
    空间复杂度：O(1)
        除了输出数组以外，空间复杂度是常数。
*/
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m == 0 || n == 0) {
            return {};
        }
        
        vector<int> res;
        res.reserve(m*n);
        int top = 0, bottom = m-1;
        int left = 0, right = n-1;

        while (left <= right && top <= bottom) {
            // 从左到右填充上边界
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }
            top++;

            // 从上到下填充右边界
            for (int i = top; i <= bottom; i++) {
                res.push_back(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                // 从右到左填充下边界
                for (int i = right; i >= left; i--) {
                    res.push_back(matrix[bottom][i]);
                }
                bottom--;
            }
            
            if (left <= right) {
                // 从下到上填充左边界
                for (int i = bottom; i >= top; i--) {
                    res.push_back(matrix[i][left]);
                }
                left++;
            }
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<vector<int>>> matrix_cases = {
        {{1,2,3}, {4,5,6}, {7,8,9}},
        {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}}
    };

    for (auto& matrix : matrix_cases) {
        cout << "Input: matrix = ";
        printArray(matrix);
        cout << endl;

        vector<int> result = solution.spiralOrder(matrix);
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }

    return 0;
}