《剑指Offer》-29.顺时针打印矩阵

题干

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如,如果输入如下矩阵:

 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

解题思路

分析题干我们知道需要对矩阵从外向里顺时针输出,我们可以转换成通俗的说法,就是一圈一圈的打印,所以我们只需要解决两个问题即可,第一个就是在什么条件下终止打印,第二个是如何打印一圈。

对于第一个问题,我们可以分析一下,假设左上角的坐标为(0, 0),第二圈的起点就是(1, 1),依次类推,第n圈的起点就是 (n-1, n-1),又由于我们每循环一圈,都可能会输出两行两列的数据,所以我们现在来考虑下最后一圈起点坐标和行数、列数之间的关系,例如:如果是 8X8 的矩阵,则最后一圈的坐标是(3, 3),行数大于两倍的行坐标,即8>3*2,如果是 9X9 的矩阵,则最后一圈的坐标是 (4, 4),行数大于两倍的行坐标,即9>4*2,列数同理,由此我们可以分析得出,只要行数和列数都大于最后一圈的起点坐标的行和列,则还需要循环一圈。

对于第二个问题,我们需要考虑一些特殊情况了,对于行列相同的矩阵,每一圈循环都会按照从左到右,从上到下,从右到左,从下到上的四个步骤完成打印,而对于一些不规则的矩阵,如行数小于列数,行数大于列数时,需要特别分析一下,有可能出现缺少后面几步的情况。

  • 如果需要执行从上到下的打印,需要循环的结束行号大于开始行号
  • 如果需要执行从右到左的打印,需要循环的结束行号大于开始行号,且结束列号大于开始列号
  • 如果需要执行从下到上的打印,不仅仅需要循环的结束号大于开始行号,而需要结束行号-开始行号>=2,且结束列号大于开始列号

到此,上面的两个问题就分析完了,可以代码实现了。

代码实现

<?php
/**
 * @param array $arr 二维数组
 * @param int $columns 列数
 * @param int $rows 行数
 */
function printMatrixClockwisely(array $arr, int $columns, int $rows)
{
    if ($arr == null || $columns == 0 || $rows == 0) {
        return;
    }
    $start = 0;
    while ($columns > $start * 2 && $rows > $start * 2) {
        printMatrixInCircle($arr, $columns, $rows, $start);
        $start++;
    }
}

/**
 * @param array $arr 二维数组
 * @param int $columns 列数
 * @param int $rows 行数
 * @param int $start 圈号
 */
function printMatrixInCircle(array $arr, int $columns, int $rows, int $start)
{
    // 从0开始,需要额外减1
    $endRow = $rows - $start - 1;
    $endColumn = $columns - $start - 1;

    // 从左至右输出
    for ($i = $start; $i <= $endColumn; $i++) {
        $num = $arr[$start][$i];
        printNum($num);
    }

    // 从上至下输出
    if ($endRow > $start) {
        for ($i = $start + 1; $i <= $endRow; $i++) {
            $num = $arr[$i][$endColumn];
            printNum($num);
        }
    }
    // 从右至左输出
    if ($endRow > $start && $endColumn > $start) {
        for ($i = $endColumn - 1; $i >= $start; $i--) {
            $num = $arr[$endRow][$i];
            printNum($num);
        }
    }

    // 从下至上输出
    if ($endColumn > $start && $endRow - $start > 1) {
        for ($i = $endRow - 1; $i > $start; $i--) {
            $num = $arr[$i][$start];
            printNum($num);
        }
    }
}

function printNum($num)
{
    printf('%3d', $num);
}


$arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]];
printMatrixClockwisely($arr, 4, 4);
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,921评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,635评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,393评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,836评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,833评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,685评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,043评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,694评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,671评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,424评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,027评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2 343

推荐阅读更多精彩内容