百度网站推广教程甘肃省建设监理协会网站

54. 螺旋矩阵

解题思路

顺时针螺旋顺序也就是“从左向右、从上向下、从右向左、从下向上” 循环。那么算法的核心就是模拟这个过程，
定义左、右、上、下 四个边界 l , r , t , b，然后按照这个顺序遍历，同时收缩边界，直到遍历完所有元素。

1. 定义左、右、上、下 四个边界 l , r , t , b
2. 从左到右遍历上边界，遍历完将上边界下移
3. 从上到下遍历右边界，遍历完将右边界左移
4. 从右到左遍历下边界，遍历完将下边界上移
5. 从下到上遍历左边界，遍历完将左边界右移
6. 重复上述步骤，直到遍历完所有元素

代码实现

//这是错的，往下看
vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(),n=matrix[0].size();int l = 0, r = n - 1, t = 0, b = m - 1;int i = 0, nums = n *m;vector<int> ans;while (i <nums) {// 向右for (int j = l; j <= r; j++) {ans.push_back(matrix[t][j]);i++;}// 向下t++;for (int j =t; j <= b; j++) {ans.push_back(matrix[j][r]);i++;}//向左r--;for (int j = r; j >= l; j--) {ans.push_back(matrix[d][j]);i++;}//向上b--;for (int j = b; j >= t; j--) {ans.push_back(matrix[j][l]);i++;}l++;}return ans;}

这段代码符合上述算法流程，但是matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]时，输出为[1, 2 ,3 ,4, 8 ,12, 11 ,10 ,9,5 ,6 ,7 ,6 ]，多输出了一个6，在向右遍历的时候，这段代码正确的将6和7加入到了ans中，但是此时i=12,l=1,r=2接着开始向下遍历执行t++后，此时t=2,b=1不满足循环条件跳过，接着向左移动执行r--后，此时r=1,l=1竟然满足循环条件，进入了循环把6又加到了ans中，所以在每一个循环中，还有一个循环条件就是i<nums，防止多输出元素。
下面这段代码才是正确的代码

vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(),n=matrix[0].size();int l = 0, r = n - 1, t = 0, b = m - 1;int i = 0, nums = n *m;vector<int> ans;while (i <nums) {// 向右for (int j = l; j <= r&&i<nums; j++) {ans.push_back(matrix[t][j]);i++;}// 向下t++;for (int j =t; j <= b&&i<nums; j++) {ans.push_back(matrix[j][r]);i++;}//向左r--;for (int j = r; j >= l&&i<nums; j--) {ans.push_back(matrix[d][j]);i++;}//向上b--;for (int j = b; j >= t&&i<nums; j--) {ans.push_back(matrix[j][l]);i++;}l++;}return ans;
}

或者说，当上边界和下边界相遇或左边界和右边界相遇时，直接跳出循环，防止多输出元素

vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(),n=matrix[0].size();int l = 0, r = n - 1, t = 0, b = m - 1;vector<int> ans;while (true) {for (int i = l; i <= r; i++) ans.push_back(matrix[t][i]); //向右if (++t > b) break;for (int i = t; i <= b; i++) ans.push_back(matrix[i][r]); // 向下if (l > --r) break;for (int i = r; i >= l; i--) ans.push_back(matrix[b][i]); // 向左if (t > --b) break;for (int i = b; i >= t; i--) ans.push_back(matrix[i][l]); //向上if (++l > r) break;}return ans;
}