算法：顺时针打印矩形（Java题解和思考过程）

雨点打透心脏的1/2处 2023-11-20 06:15 106阅读 0赞

## 题目 ##

[牛客网题目链接][Link 1]  
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.

## 思考过程 ##

1.  首先想到有点像剥洋葱，一层一层剥开，每次都将最外面的一层撕开（in this case, 就是吧最外面一层的数字顺时针加进result里面）
2.  其次要想如何定义这个“最外面的一层”。定义一个矩阵内的矩型其实就是需要左上和右下两个坐标，分别为（top,left）(bottom,right)
3.  所以我们就可以开始定义这四个变量left right top bottom。 left top都可以直接初始化为0，bottom和right分别为矩阵的长度和矩阵每行的长度（当然先判定这两个不为0，不然就是空矩阵）
4.  所以第一层循环是while循环，每次循环就是剥掉外面一层的过程，所以每次top++;bottom–;left++;right–;相当于缩小一圈的范围
5.  之后就是将外圈顺时针加入到res里面了，这力要注意，如果矩阵的行和列是单数的话，那么最中心水平或者垂直方向的top,bottom或者left,right会想等，这个时候就不需要再重复输出了
6.  最后一个小点就是顺时针以起始位置下方一个元素结束，所以代码里是：

for(int i=bottom-1;i>=top+1;i--){

## 完整代码 ##

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> printMatrix(int [][] matrix) {
               ArrayList<Integer> res = new ArrayList<>();
               if(matrix.length==0||matrix[0].length==0) return res;
               int left=0,right=matrix[0].length-1,top = 0, bottom =matrix.length-1;
               
               while(top<=bottom&&left<=right){
                   for(int i=left;i<=right;i++){
                       res.add(matrix[top][i]);
                   }
                   for(int i=top+1;i<=bottom;i++){
                       res.add(matrix[i][right]);
                   }
                   if(top<bottom){
                       for(int i=right-1;i>=left;i--){
                           res.add(matrix[bottom][i]);
                       }
                   }
                   if(left<right){
                       for(int i=bottom-1;i>=top+1;i--){
                           res.add(matrix[i][left]);
                       }
                   }
                   top++;bottom--;left++;right--;
               }
               return res;
        }
    }

[Link 1]: https://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking