康瑞部落

Spiral Matrix

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

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

解题思路：

分析题，没有什么难度，注意防止重复读取。读了“7”字形之后要判断。下面是代码：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> result;
        int rows = matrix.size();
        if(rows == 0){
            return result;
        }
        int cols = matrix[0].size();
        if(cols == 0){
            return result;
        }
        
        int rowsRead = 0;
        int colsRead = 0;
        
        while(rowsRead<(rows+1)/2 && colsRead<(cols + 1)/2){
            //输出上层边
            for(int i = colsRead; i < cols - colsRead; i++){
                result.push_back(matrix[rowsRead][i]);
            }
            //输出最右边
            for(int i = rowsRead + 1; i < rows - rowsRead; i++){
                result.push_back(matrix[i][cols - colsRead - 1]);
            }
            //若行数为奇数，并读到了中间一行，退出
            if((rowsRead + 1)*2 > rows){
                break;
            }
            //若列数为奇数，且读到了中间一列，跳出
            if((colsRead + 1)*2 > cols){
                break;
            }
            //输出最低边
            for(int i = cols - colsRead - 2; i>=colsRead; i--){
                result.push_back(matrix[rows - rowsRead - 1][i]);
            }
            //输出最左边
            for(int i = rows - rowsRead - 2; i>=rowsRead+1;i--){
                result.push_back(matrix[i][colsRead]);
            }
            rowsRead++;
            colsRead++;
        }
        
        return result;
    }
};

二次刷题（update in 2015-07-29）

同样在“7”字形之后忘记判断了，导致重复读取。这里之用一个变量：layer表示目前读那一层。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        
        int m = matrix.size();
        if(m==0){
            return result;
        }
        int n = matrix[0].size();
        if(n==0){
            return result;
        }
        int layer = 0;  //已经读取的层次
        while(result.size() < m * n){
            //读取北边
            for(int i=layer; i<n-layer; i++){
                result.push_back(matrix[layer][i]);
            }
            //读取东边，注意读北边的时候将最上边的那个读取了
            for(int i=layer + 1; i<m-layer; i++){
                result.push_back(matrix[i][n - 1 - layer]);
            }
            if(result.size() >= m * n){
                break;
            }
            //读取南边，注意读东边的时候最右边那个已经读取了
            for(int i=n - 1 - layer - 1; i>=layer; i--){
                result.push_back(matrix[m - 1 - layer][i]);
            }
            //读取西边，注意读取北边和南边的时候，最上边和最下边的那个已经读取了
            for(int i=m - 1 - layer - 1; i>layer; i--){
                result.push_back(matrix[i][layer]);
            }
            layer++;
        }
        
        return result;
    }
};