当前位置：首页 > article >正文

[Day 16]螺旋遍历二维数组

article 2025/2/8 14:29:16

今天我们看一下力扣上的这个题目：146.螺旋遍历二维数组

题目描述：

给定一个二维数组 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题是差不多一样的，我前面也有讲过，大家可以先做做。本道题是一个螺旋矩阵的题，面对这样的题，我们应该想到的是画个图遍历一下这个过程，我们可以得到如下的图：
首先我们先定义一个新数组用来存储数据的并判断一下这个二维数组是否为空，如果是空就返回空数组。如果第一行也是空，那么也是返回空。

  vector<int> res;
        if (array.empty() || array[0].empty()) {
            return res;
        }

接下来我们可以分为：从左到右遍历，从上到下遍历，从右到左遍历，从下到上遍历
在这里插入图片描述
1.从左到右遍历：
我们先定义一个left、right来遍历左右，定义top、bottom为上下。当top<=bottom或者left<=right时，循环一直继续。

		int left = 0;//初始化左边
        int right = array[0].size() - 1;//初始化右边为第一行数组最后一个数
        int top = 0;//初始化top为从上到下第一个
        int bottom = array.size() - 1;//初始化下边为最下列的数
        for (int i = left; i <= right; i++) {//定义i从最左边开始遍历，一直到第一行最后一个数
                res.push_back(array[top][i]);//二维数组横坐标不变，纵坐标变化尾插到新数组中
            }
            top++;//top向前走继续遍历第二行

在这里插入图片描述
2.从上到下遍历
列不变，行改变

for (int i = top; i <= bottom; i++) {//i从top开始，到bottom结束
                res.push_back(array[i][right]);//尾插到right这一列
            }
            right--;//列数减小

3.从右到左遍历
行不变，列变

 if (top <= bottom) {//判断一下top>bottom时，证明遍历完了，直接返回
                for (int i = right; i >=left; i--) {//i从右边开始，一直到大于等于left，进行--的操作
                    res.push_back(array[bottom][i]);//尾插到bottom行，i列
                }
                bottom--;//bottom向上移动减少
            }

4.从下到上遍历
列不变，行变

    if (left <= right) {//当左边大于右边的时候，没有要遍历的了
                for (int i = bottom; i >= top; i--) {//i从bottom开始遍历到top
                    res.push_back(array[i][left]);//尾插到left列
                }
            }
           left++;//完了之后left向左移动加加

最后，返回这个新数组res

完整代码

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> res;
        if (array.empty() || array[0].empty()) {
            return res;
        }

        int left = 0;
        int right = array[0].size() - 1;
        int top = 0;
        int bottom = array.size() - 1;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                res.push_back(array[top][i]);
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                res.push_back(array[i][right]);
            }
            right--;
            if (top <= bottom) {
                for (int i = right; i >=left; i--) {
                    res.push_back(array[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.push_back(array[i][left]);
                }
            }
           left++;
        }
        return res;
    }
};