剑指offer—顺时针打印矩阵 解答

剑指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.

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

思路

方法一:从外到内逐层输出

使用一个变量记录层数,每层循环内分别添加上面、右边、下面、左边的数到集合

1.怎么计算层数

画图分析可知,循环数就是层数,并且循环数由矩阵中较短的一边决定

  • 如果较短的一边为偶数,则层数为长短除以2(一次循环两边各走一次)
  • 如果较短的一边为奇数,除以2后会取低一位(5/2=2),中间会多出一行或者一列,这个时候我们需要根据多出来的是行还是列来进行遍历并添加到集合中
2.四边怎么添加元素
  • 上面添加第一个到行倒数第二个
  • 右边添加列第一个到列倒数第二个
  • 下面从右向左添加行最后一个到行第二个
  • 左边从下到上添加列最后一个到列第二个

方法二:魔方逆时针旋转

可以模拟魔方逆时针旋转的方法,一直做取出第一行的操作

例如 

1 2 3

4 5 6

7 8 9

输出并删除第一行后,再进行一次逆时针旋转,就变成:

6 9

5 8

4 7

继续重复上述操作即可。

8 7

5 4

继续重复上述操作即可。

4 5

代码

这里仅实现方法一代码,感兴趣的可以自己实现方法二

  • 优化前
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> nums = new ArrayList<Integer>();
        if(matrix.length==0)
            return nums;
        int c = matrix.length<matrix[0].length?matrix.length/2:matrix[0].length/2;//获取较小一边后计算循环数
        for(int i=0;i<c;i++){
            for(int up=i;up<matrix[i].length-i-1;up++){//上面
                nums.add(matrix[i][up]);
            }
            for(int right=i;right<matrix.length-i-1;right++){//右边
                int l = matrix[i].length-i-1;
                nums.add(matrix[right][l]);
            }
            for(int bo=matrix[i].length-i-1;bo>i;bo--){//下面
                int l = matrix.length-i-1;
                nums.add(matrix[l][bo]);
            }
            for(int left=matrix.length-i-1;left>i;left--){//左边
                nums.add(matrix[left][i]);
            }
        }
        if((matrix.length&1)==1&&matrix.length<=matrix[0].length){//如果较短一边为奇数并且是行短
            for(int i=c;i<matrix[0].length-c;i++)
                nums.add(matrix[c][i]);
        }else if((matrix[0].length&1)==1&&matrix[0].length<matrix.length){//如果较短一边为奇数并且是列短
            for(int i=c;i<matrix.length-c;i++)
                nums.add(matrix[i][c]);
        }
        return nums;
    }
}
  • 优化后
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        if(matrix.length==0) return nums;
        int c = matrix.length<matrix[0].length?matrix.length/2:matrix[0].length/2;
        for(int i=0;i<c;i++){
            int l1 = matrix[i].length-i-1; 
            int l2 = matrix.length-i-1;
            for(int up=i;up<l1;up++) nums.add(matrix[i][up]);
            for(int right=i;right<l2;right++) nums.add(matrix[right][l1]);
            for(int bo=l1;bo>i;bo--) nums.add(matrix[l2][bo]);
            for(int left=l2;left>i;left--) nums.add(matrix[left][i]);
        }
        if((matrix.length&1)==1&&matrix.length<=matrix[0].length){
            for(int i=c;i<matrix[0].length-c;i++) nums.add(matrix[c][i]);
        }else if((matrix[0].length&1)==1&&matrix[0].length<matrix.length){
            for(int i=c;i<matrix.length-c;i++) nums.add(matrix[i][c]);
        }
        return nums;
    }
}