LeetCode Spiral Matrix

LeetCode 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].


把矩阵按螺旋形打印出来,很有意思的一道题,我隐隐约约记得本科找工作的时候有这么一道笔试题。中等难度,需要多次调试修改才能AC。

思路是标记矩阵的左上角和右下角两个坐标,分别为sx,sy和tx,ty。然后每次从左上角开始,绕一圈,则起点sx,sy都加1,终点tx,ty都减1。如此循环,直到终点跑到起点上面去了。

需要注意后两个for循环的条件,要依次同时满足上一个条件,因为有可能遇到行向量(第三个for)或者列向量(第四个for)。完整代码如下:

class Solution {
public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
		vector<int> vSpiralOrder;
		if (matrix.size() == 0)return vSpiralOrder;
		int sx = 0, sy = 0, tx = matrix.size(), ty = matrix[0].size();
		while (true) {
			for (int j = sy; j < ty; j++)
				vSpiralOrder.push_back(matrix[sx][j]);
			for (int i = sx + 1; i < tx; i++)
				vSpiralOrder.push_back(matrix[i][ty - 1]);
			for (int j = ty - 2; sx + 1 < tx && j >= sy; j--) // 满足上一个条件sx+1<tx
				vSpiralOrder.push_back(matrix[tx - 1][j]);
			for (int i = tx - 2; ty - 2 >= sy && i > sx; i--) // 满足上一个条件ty-2>=sy
				vSpiralOrder.push_back(matrix[i][sy]);
			sx++;
			sy++;
			tx--;
			ty--;
			if (sx >= tx || sy >= ty)break;
		}
		return vSpiralOrder;
	}
};

本代码提交AC,用时0MS。

二刷。更安全的做法(https://discuss.leetcode.com/topic/3713/super-simple-and-easy-to-understand-solution):

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(matrix.empty() || matrix[0].empty()) return ans;
        int start_row = 0, start_col = 0, end_row = matrix.size() - 1, end_col = matrix[0].size() - 1;
        while(start_row <= end_row && start_col <= end_col) {
            for(int j = start_col; j <= end_col; ++j) {
                ans.push_back(matrix[start_row][j]);
            }
            ++start_row;
            for(int i = start_row; i <= end_row; ++i) {
                ans.push_back(matrix[i][end_col]);
            }
            --end_col;
            if(start_row <= end_row) { // 防止行向量
                for(int j = end_col; j >= start_col; --j) {
                    ans.push_back(matrix[end_row][j]);
                }
            }
            --end_row;
            if(start_col <= end_col) { // 防止列向量
                for(int i = end_row; i >= start_row; --i) {
                    ans.push_back(matrix[i][start_col]);
                }
            }
            ++start_col;
        }
        return ans;
    }
};

本代码提交AC,用时0MS。

One thought on “LeetCode Spiral Matrix

  1. Pingback: LeetCode Spiral Matrix II | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *