剑指Offer（十九）——顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

例如，如果输入如下4 X 4矩阵：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思想：

一圈一圈的打印，这道题难点在于何时中止打印。

图为在矩阵中某一圈，length为矩阵长度，width为矩阵宽度,坐标值为数组下标。

对于我们这道题来说，只要有内圈可以进入下一圈就是以第一圈(0,0) 第二圈 (1,1) ……的规律做每一圈的起点

现在考虑以下标(i,i)为起点的一圈，其图像为length为矩阵长度，width为矩阵宽度

打印过程是四个for循环以此为上-》右-》下-》左顺时针遍历

按照图我们开始遍历第i圈

//注意四个角的元素不能重复

//上 行i 列i  length-i-1

for (int j=i; j <= length-i-1; j++) {

	result.push_back(matrix[i][j]);

}

//右 列 length-i-1 行i+1

for (int j= i+1; j <= width - i - 1; j++) {

	result.push_back(matrix[j][length-i-1]);

}

//下 行width-i-1  列length-2-1  到i

for (int j = length-i-2; j >= i; j--) {

    result.push_back(matrix[width-i-1][j]);

}

//左 列i  行 width-i-2  到 i+1

for (int j = width-i-2; j > i; j--) {

	result.push_back(matrix[j][i]);

}

现在一圈完了，下一圈会不会有什么突发状况？

思考：假设下一圈就结束循环了，那么可能遇到什么情况，下一圈不再是一个完整矩形(指的是长宽都大于1的矩阵)而是有四种可能。我们之所以分析是要看这几种情况对我们四个for循环是否都适用

1.没有元素

2.只有一个元素

3.只有一行元素

4.只有一列元素

好的，现在我们知道了所有可能的形状。那进入到这几种情况我们就要考虑了。

1.本圈矩形的长宽只要任意一个为0就结束循环，没有元素了 条件宽0长0 length-2i<=0或width-2i<=0

此时直接跳出循环即可，四个for循环都不满足

2.只有一个元素和只有一行元素就是我们只需要进行顺势针打印的上面部分,此时条件是宽1长若干 (width-2i==1且length-2i大于1)化简此时 width=2i-i

//打印一行没有问题，按道理来说是不是之后的打印都不应该做

观察下

右面打印的判断条件 int j= i+1; j <= width - i - 1; j++ 因为宽度为1 初始 width为2i+1 代入for循环判断不满足 j=i+1< i条件

下面打印的判断条件 int j = length-i-2; j >= i; j-- 假设length无穷大,那可进入for循环从左到右打印

左面打印的判断条件类似右面,因宽度为1本身就可限制

总结：因长度大于1,宽度等于1出现重复打印情况如下：

所以我们在顺时针上面对应的for结束，右侧下面左侧的for可以避免。但是我们下侧for循环就需要有判断条件，为 if(宽度为1则下侧for循环不执行) ，

3.只有一行元素就是我们可以顺时针打印上面和左面的部分，此时条件是宽若干长1 (width-2i大于1且length-2i==1)

类似一行的情况，要给左侧for循环加判断条件 if(长度为1可以不打左侧，因为右侧打完了)

ok，那基于上面的分析我们知道了只要下一圈有元素，我们就可以i++,四个for遍历下一圈，加上我们的if条件。即使出现特殊情况也不必担心。

那下一圈有元素的条件就是非没有元素的条件(length-2*i>0)&&(width-2*i>0)

综上所述，总结一下对于单行、单列要考虑左右、上下打印条件的相互制约。

给出代码和运行截图：

 class Solution {

 public:

     static vector<int> printMatrix(vector<vector<int> > matrix) {

         if (matrix.size() == ) return vector<int>();

         int width = matrix.size(), length = matrix[].size();//r,c为矩阵长宽

         int i = ;

         vector<int> result;

         while ((length -  * i > ) && (width -  * i > ))

         {

             //上侧

             for (int j = i; j <= length - i - ; j++) {

                 result.push_back(matrix[i][j]);

             }

             //右侧

             for (int j = i + ; j <= width - i - ; j++) {

                 result.push_back(matrix[j][length - i - ]);

             }

             //下侧

             if (width -  * i != ) {//宽度为1不要有右到左打印一遍了，上侧已经打了

                 for (int j = length - i - ; j >= i; j--) {

                     result.push_back(matrix[width - i - ][j]);

                 }

             }

             //左侧

             if (length -  * i != ) {//长度为1不要再由下到上打印一遍了，右侧从上到下打了

                 for (int j = width - i - ; j > i; j--) {

                     result.push_back(matrix[j][i]);

                 }

             }

             i++;

         }

         return result;

     }

 };

运行截图：

附上一个小知识点:vectot<int> 的push_back函数会像数组尾部填数据。预先申请好大小后vector<int> a(5); 用 push_back时会扩容的去填,前面的5个数都是0。

我误认为要先申请空间才能向里添加数据了。

最后，感谢阅读文章，如有疏漏，欢迎指正。

现在转了一圈，要结束了，结束时会出现四种可能,一行、一列、一个、无元素

对于一行的情况，其条件是只

巴特西

剑指Offer（十九）——顺时针打印矩阵

题目描述

最新文章

热门文章