[LeetCode][54]【学习日记】螺旋遍历二维数组

题目

螺旋遍历二维数组

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
示例 1：
输入：array = [[1,2,3],[8,9,4],[7,6,5]] 输出：[1,2,3,4,5,6,7,8,9]
示例 2：
输入：array = [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

限制：

0 <= array.length <= 100 0 <= array[i].length <= 100
注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/

解法：边界检查

• 设置上下左右的边界然后循环遍历即可，每次都输出矩阵的最外一层。
  

vector<int> spiralArray(vector<vector<int>>& matrix) {
        vector<int> ans;
        if(!matrix.size() || !matrix[0].size()) return ans;
        int eleNum = matrix.size() * matrix[0].size();

        int maxUpper=0, maxLower=matrix.size()-1, maxLeft=0, maxRight=matrix[0].size()-1;
        while(true){
            if(ans.size()==eleNum) break;
            else if(ans.size()!=eleNum && maxUpper==maxLower && maxLeft==maxRight){
                ans.push_back(matrix[maxUpper][maxLeft]);
                break;
            }
            else if(ans.size()!=eleNum && maxUpper==maxLower && maxLeft!=maxRight){//上下边界碰撞 且 未全部填入
                for(int i=maxLeft; i<=maxRight; ++i) ans.push_back(matrix[maxUpper][i]);
                break;
            }
            else if(ans.size()!=eleNum && maxUpper!=maxLower && maxLeft==maxRight){
                for(int i=maxUpper; i<=maxLower; ++i)  ans.push_back(matrix[i][maxLeft]);
                break;
            }
            for(int i=maxLeft; i<=maxRight; ++i) ans.push_back(matrix[maxUpper][i]);
            for(int i=maxUpper+1; i<=maxLower; ++i) ans.push_back(matrix[i][maxRight]);
            for(int i=maxRight-1; i>=maxLeft; --i) ans.push_back(matrix[maxLower][i]);
            for(int i=maxLower-1; i>maxUpper; --i) ans.push_back(matrix[i][maxLeft]);
            maxUpper++; maxLeft++; maxLower--; maxRight--;
           
        }
        return ans;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

在这个例子中，由于边界的递增时间设置得不够好，判断时间也不够好，所以增加了很多额外的判断，也就是先检查 ans.size()!=eleNum 后进行边界碰撞的判断：

1. 上下边界和左右边界碰撞，但是输出元素数量小于矩阵中元素数量时，证明此矩阵为方阵，此时剩下最中间的元素没有输出
2. 上下边界碰撞但是左右边界没有碰撞，且输出元素数量小于矩阵中元素数量时，则此矩阵为行数小于列数的矩阵，画图可知，此时向右输出剩下的元素，直到碰到右边界即可
3. 上下边界没有碰撞但是左右边界碰撞，且输出元素数量小于矩阵中元素数量时，则此矩阵为行数大于列数的矩阵，画图可知，此时向右输出一个元素，然后向下输出剩下的元素，直到碰到下边界即可

解法：简化的边界检查版本

设置好边界的更新时间和碰撞检查的时间，可以优化掉判断代码。

• 因为在上面的做法中，是每剥一层才将边界都一起更新了，然后进行边界碰撞的判断，而且是使用边界相等进行碰撞检查。
  • 边界相等进行碰撞检查的缺点是，在边界相等时可能还有元素未遍历到，此时退出则结果错误，继续遍历则面临较多种不同的边界相等的情况，需要很多判断分支。
• 而如果在每一边遍历后立刻先更新对应边界然后检查，而且使用边界是否大于检查，则不需要太多分支。
  • 先更新后检查，可以保证刚刚每更新前输出的元素没有越界，使用大于进行检查，则避免了使用相等进行检查时可能出现元素未全部遍历到的问题。

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array)
    {
        if (array.empty()) return {};
        int l = 0, r = array[0].size() - 1, t = 0, b = array.size() - 1;
        vector<int> res;
        while(true)
        {
            for (int i = l; i <= r; i++) res.push_back(array[t][i]); // left to right
            if (++t > b) break;
            for (int i = t; i <= b; i++) res.push_back(array[i][r]); // top to bottom
            if (l > --r) break;
            for (int i = r; i >= l; i--) res.push_back(array[b][i]); // right to left
            if (t > --b) break;
            for (int i = b; i >= t; i--) res.push_back(array[i][l]); // bottom to top
            if (++l > r) break;
        }
        return res;
    }
};

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/lht9s3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26