54. 螺旋矩阵

shayue 2019-02-11 原文

题目描述

给定一个包含 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]

算法

外一层，里一层的递归插入要返回的向量中。
执行递归插入操作的函数是void insert_to_vec(vector<vector<int>>& matrix, int left_top_row, int left_top_col, int right_bottom_row, int right_bottom_col)，
它包含5个参数：
1. 矩阵
2. 左上角的行
3. 左上角的列
4. 右下角的行
5. 右下角的列
left_top_row > right_bottom_row || left_top_col > right_bottom_col是递归的中止条件，
left_top_row == right_bottom_row 和 left_top_col == right_bottom_col是特殊边界，
整个插入按照左上到右上，右上到右下，右下到左下，左下到左上的流程走完，
然后进行里一层的插入，即调用insert_to_vec(matrix, left_top_row+1, left_top_col+1, right_bottom_row-1, right_bottom_col-1);.

代码

class Solution {
public:
    // 这是要返回的答案
    vector<int> ansVec;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // row是矩阵的行数
        int row = matrix.size();
        
        if (row == 0)
            return ansVec;
        
        if (row == 1)
            return matrix[0];
        
        // col是矩阵的列数
        int col = matrix[0].size();
        
        if (col == 1)
        {
            for (int j = 0; j < row; j++)
                ansVec.push_back(matrix[j][0]);
            return ansVec;
        }
        
        insert_to_vec(matrix, 0, 0, row-1, col-1);
        return ansVec;
    }
    
    void insert_to_vec(vector<vector<int>>& matrix, int left_top_row, int left_top_col, int right_bottom_row, int right_bottom_col)
    {
        if (left_top_row > right_bottom_row || left_top_col > right_bottom_col)
            return;
        
        if (left_top_row == right_bottom_row)
        {
            for (int i = left_top_col; i <= right_bottom_col; i++)
                ansVec.push_back(matrix[left_top_row][i]);
            return;
        }
        
        if (left_top_col == right_bottom_col)
        {
            for (int i = left_top_row; i <= right_bottom_row; i++)
                ansVec.push_back(matrix[i][left_top_col]);
            return;
        }
        
        for(int i = left_top_col; i <= right_bottom_col; i++)
            ansVec.push_back(matrix[left_top_row][i]);
        
        for(int i = left_top_row + 1; i <= right_bottom_row; i++)
            ansVec.push_back(matrix[i][right_bottom_col]);
        
        for(int i = right_bottom_col - 1; i >= left_top_col; i--)
            ansVec.push_back(matrix[right_bottom_row][i]);
        
        for(int i = right_bottom_row - 1; i > left_top_row; i--)
            ansVec.push_back(matrix[i][left_top_col]);
        
        insert_to_vec(matrix, left_top_row+1, left_top_col+1, right_bottom_row-1, right_bottom_col-1);
    }
};