关于面试:每日一题螺旋矩阵

题目

给定一个 m x n 大小的矩阵（m 行，n 列），按螺旋的程序返回矩阵中的所有元素。

数据范畴：0≤n,m≤10，矩阵中任意元素都满足 ∣val∣≤100

要求：空间复杂度 O(nm)，工夫复杂度 O(nm)

示例 1

 输出：[[1,2,3],[4,5,6],[7,8,9]]
返回值：[1,2,3,6,9,8,7,4,5]

示例 2

 输出：[]
返回值：[]

思路

• 首先排除矩阵为空的状况的非凡状况。
• 设置矩阵的四个边界值，开始筹备螺旋遍历矩阵，遍历的截止点是左右边界或者高低边界重合。
• 首先对最下面一排从左到右进行遍历输入，达到最左边后第一排就输入完了，上边界相应就往下一行，要判断高低边界是否相遇相交。
• 而后输入到了左边，正好就对最左边一列从上到下输入，到底后最左边一列曾经输入完了，右边界就相应往左一列，要判断左右边界是否相遇相交。
• 而后对最上面一排从右到左进行遍历输入，达到最右边后最下一排就输入完了，下边界相应就往上一行，要判断高低边界是否相遇相交。
• 而后输入到了右边，正好就对最右边一列从下到上输入，到顶后最右边一列曾经输入完了，左边界就相应往右一列，要判断左右边界是否相遇相交。
• 反复上述遍历操作直到循环完结。

解答代码

#include <vector>
class Solution {
public:
    /**
     * @param matrix int 整型 vector<vector<>> 
     * @return int 整型 vector
     */
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        // write code here
        auto row_size = matrix.size();
        if (row_size == 0) {return vector<int>{};
        }
        auto col_size = matrix[0].size();
        // 上边界
        int top = 0;
        // 下边界
        int bottom = row_size - 1;
        // 左边界
        int left = 0;
        // 右边界
        int right = col_size - 1;
        vector<int> res;
        while (top <= bottom && left <= right) {
            // 从左到右遍历上边界
            for (int i = left; i <= right; i++) {res.push_back(matrix[top][i]);
            }
            // 上边界下移
            ++top;
            if (top > bottom)
                break;
            // 从上到下遍历右边界
            for (int i = top; i <= bottom; i++) {res.push_back(matrix[i][right]);
            }
            // 左移右边界
            --right;
            if (right < left)
                break;
            // 从右到左遍历下边界
            for (int i = right; i >=left; i--) {res.push_back(matrix[bottom][i]);
            }
            // 上移下边界
            --bottom;
            if (bottom < top)
                break;
            // 从下到上遍历左边界
            for (int i = bottom; i >= top; i--) {res.push_back(matrix[i][left]);
            }
            // 右移左边界
            ++left;
            if (left > right)
                break;
        }
        return res;
    }
};