美文网首页剑指offer
剑指offer——顺时针打印矩阵

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

作者: source201 | 来源:发表于2019-07-02 20:26 被阅读0次

    剑指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)printMatrix函数是程序的主体函数,负责调用顺时针获取矩阵perMatrix函数和去除矩阵最外围shortMatrix函数
    (2) perMatrix函数:主要功能顺时针获取矩阵的最外围数值。主要分四个步骤,(红箭头)首先获取第一行的数值,(橙箭头)然后判断矩阵是否超过2行,如果超过则从第二行到倒数第二行获取行最后的数值。(黄箭头)接着如果矩阵行数大于1,从右向左获取最后一行的数值。(绿箭头)最后,如果矩阵超过两行,并且行中的元素大于,1,从第二行到倒数第二行获取行第一个数值。


    perMatrix函数示意图.png

    (3) shortMatrix函数:新建一个行数为原矩阵行数减2的矩阵result,然后从1行(有第0行)到倒数第2行遍历,如果行数超过2,则读取原矩阵当前行的1列到倒数第二列。接着遍历result,如果存在空行,记录行数。最后,调用delnull函数,得到没有空行的矩阵。
    (4)delnull函数:构建一个行数为原矩阵行数-ArraList长度的矩阵result,然后遍历原矩阵,如果行非空,则赋给result。

    代码

    package jian;
    
    import java.util.ArrayList;
    
    public class Solution {
    
        public ArrayList<Integer> printMatrix(int [][] matrix) {
            ArrayList<Integer> re=new ArrayList<Integer>();
            while(matrix.length>0){
                ArrayList<Integer> tmp=perMatrix(matrix);
                re.addAll(tmp);
                matrix=shortMatrix(matrix);
            }
    
            for(int i =0;i<re.size();i++){
                System.out.print("\t"+re.get(i));
            }
            return re;
        }
    //    保存矩阵顺时针最外围数据
        public ArrayList<Integer> perMatrix(int [][] matrix){
            ArrayList<Integer> re=new ArrayList<Integer>();
            for(int y =0;y<matrix[0].length;y++){
                re.add(matrix[0][y]);
            }
            if(matrix.length>2){
                for(int x=1;x<matrix.length-1;x++){
                    re.add(matrix[x][matrix[x].length-1]);
                }
            }
            if(matrix.length>1){
                for(int y =matrix[matrix.length-1].length-1;y>-1;y--){
                    re.add(matrix[matrix.length-1][y]);
                }
            }
            if(matrix.length>2) {
                for (int x = matrix.length - 2; x > 0; x--) {
                    if(matrix[x].length>1){
                        re.add(matrix[x][0]);
                    }
    
                }
            }
            return re;
        }
        //缩小矩阵
        public int[][] shortMatrix(int[][] matrix){
            int[][] result={};
            if(matrix.length>2) {
                result = new int[matrix.length - 2][];
                for (int x = 1; x < matrix.length - 1; x++) {
                    if (matrix[x].length >2){
                        int[] tmp = new int[matrix[x].length - 2];
                        for (int y = 1; y < matrix[x].length - 1; y++) {
                            tmp[y - 1] = matrix[x][y];
                        }
                        result[x - 1] = tmp;
                    }else{
                        result[x-1]=null;
                    }
                }
            }
            ArrayList<Integer> keys=new ArrayList<Integer>();
            for(int i=0;i<result.length;i++){
                if(result[i]==null){
                    keys.add(i);
                }
            }
            result=delNull(result,keys);
            return result;
        }
        //矩阵去空行
        public int[][] delNull(int[][] matrix,ArrayList<Integer> keys){
            int[][] result= new int[matrix.length-keys.size()][];
            int num=0;
            for(int i = 0;i<matrix.length;i++){
                if(!keys.contains(i)){
                    result[num]=matrix[i];
                    num=num+1;
                }
            }
            return result;
        }
    }
    

    相关文章

      网友评论

        本文标题:剑指offer——顺时针打印矩阵

        本文链接:https://www.haomeiwen.com/subject/lxothctx.html