如何顺时针打印一个二维矩阵

54 阅读 0 评论 36 点赞

我是靠谱客的博主沉默信封，最近开发中收集的这篇文章主要介绍如何顺时针打印一个二维矩阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

昨天去网易公司面试，面试官给了一道题，以前好像见过类似的题目，和面试官讨论了半天，思路是正确的，可是最后还是没能够写出满意的代码，今天没有其他事，就来梳理一下吧！
题目是这样的：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如：输入矩阵如下：

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。其实这道题目完全没有涉及复杂的数据结构和高级的算法，看起来倒像是一个很简单的问题，但实际上解决这个问题，会在代码中包含多重循环，并且还需要判断多个边界条件，如果再把问题考虑的很清楚之前就开始写代码，不可避免越写越混乱，结果一团糟，因此解决这个问题的关键在于首先要形成清晰的解决思路，并把复杂的问题分解成若干个简单的问题。（当时怎么就没有想到呢！！！）
当遇到一个比较复杂的问题的时候，可以利用图形来帮助我们思考，由于是以从外圈到内圈的顺序依次打印，我们可以把矩阵想象成若干个圆圈，我们可以用一个圆圈来打印矩阵，每一次循环打印矩阵中的一个圆圈。
接下来分析循环结束的条件假设这个矩阵的行数是rows，列数是columns，打印第一圈的左上角的坐标是（1，1），第二圈的左上角的坐标是（2，2），以此类推。我们注意到，左上角的坐标中行标和列标总是相同的，于是可以在矩阵中选取左上角为（start，start）的一圈作为我们分析的目标。
对于一个5X5的矩阵，最后一圈只有一个数字，对应的坐标是（2，2），我们发现5>2X2。对于一个6X5的矩阵，最后一圈只有一列，其左上角的坐标依然是（2，2）。我们发现5>2X2依然成立，于是我们得出，让循环继续的条件是columns>startX x2,并且rows>starty x2,so我们可以用以下的循环来打印矩阵：

void PrintMaxtrixClockwisely(int** numbers,int rows,int columns){
    if(numbers == null || columns<=0 || rows<=0)
            return error;
    int start = 0 ;
    while(columns>start*2 && rows>start*2){
        PrintMatrix(numbers,columns,rows,start);
        ++start;
    }
}

接着考虑如何打印一圈的功能，即如何实现PrintMatrix.我们可以把打印一圈分成为四个步骤，第一个从左到右打印一行，第二步从上到下打印一列，第三步从右到左打印一行，第四个从下向上打印一列。每一步根据其实坐标和终止条件打印一行或者一列。
不过值得注意的是，最后一圈有可能退化成只有一行或者一列，甚至只剩下一个数字，因此打印这样的一圈就不再需要四步。
因此，我们要仔细分析打印时每一步的前提条件:

第一步总是需要的，因为打印一圈至少有第一步；
第二步的前提条件是终止行号大于起始行号；
第三步的打印的前提条件是圈内至少有两行两列，也就是说除了要求终止行号大于起始行号之外，还要求终止列号大于起始列号；
打印第四步的前提条件是至少有三行两列，因此要求终止行号比起始行号至少大于2，同时终止列号大于起始列号。
通过以上的分析，我们可以写出以下的代码：

void PrintMatrix(int** numbers,int rows,int columns,int start){
    int endX = columns-1-start;
    int endY = rows-1-start;
    //从左到右打印一行
    for(int i=0;i<=endX;++i){
        int number = numbers[start][i];
        printf("%d ",number);
    } 
    //从上到下打印一列
    if(start<endY){
        for(int i=start+1;i<=endY;++i){
            int number = number[i][endX];
            printf("%d ",number);
        }
    } 
    if(start<endY && start<endY){
        for(int i=endX-1;i>=start;--i){
            int number = numbers[endY][i];
            printf("%d",number);
        }
    }
    if(start<endY-1 && start<endX){
        for(int i=endY-1;i>=start;--i){
            int number = numbers[i][start];
            printf("%d",number);
        }
    }
}