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

By AverageJoeWang
 标签:

顺时针打印矩阵

  • 题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 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.

  • 解题思路

由于题目是以从外圈到内圈的顺序依次打印,在矩阵中标注一圈作为分析的目标。设矩阵的宽度为cols,而其高度为rows。选取左上角坐标为(startX, startY),右下角坐标为(endX, endY)的一个圈来分析。

由于endX和endY可以根据startX、startY以及columns、rows来求得,因此此时我们只需要引入startX和startY两个变量。我们可以想象有一个循环,在每一次循环里我们从(startX, startY)出发按照顺时针打印数字。

接着分析这个循环结束的条件。对一个5×5的矩阵而言,最后一圈只有一个数字,对应的坐标为(2, 2)。我们发现5 > 2 2。对一个6×6的矩阵而言,最后一圈有四个数字,对应的坐标仍然为(2, 2)。我们发现6 > 2 2依然成立。于是我们可以得出,让循环继续的条件是“cols > startX 2 && rows > startY 2”。

接下来我们分析如何按照顺时针的顺序打印一圈的数字。我们可以分四步来打印:第一步是从左到右打印一行,第二步是从上到下打印一列,第三步从右到左打印一行,最后一步是从下到上打印一列。也就是我们把打印一圈数字这个问题,分解成四个子问题。
值得注意的是,最后一圈可能退化成只有一行、只有一列、甚至只有一个数字,因此打印这样的一圈就不需要四步了。

  • 代码实现
import java.util.ArrayList;
public class Solution {
       ArrayList<Integer> list = new ArrayList<>();

    public ArrayList<Integer> printMatrix(int[][] matrix) {
        int rows = matrix.length;
        int columns = matrix[0].length;
        int start = 0;
        while (rows > start * 2 && columns > start * 2) {
            printMatrixInCircle(matrix, rows, columns, start);
            start++;
        }
        return list;
    }

    public void printMatrixInCircle(int[][] matrix, int rows, int columns, int start) {
        // 从左到右打印一行
        for (int i = start; i < columns - start; i++)
            list.add(matrix[start][i]);
        // 从上到下打印一列
        for (int j = start + 1; j < rows - start; j++)
            list.add(matrix[j][columns - start - 1]);
        // 从右到左打印一行
        for (int m = columns - start - 2; m >= start && rows - start - 1 > start; m--)
            list.add(matrix[rows - start - 1][m]);
        // 从下到上打印一列
        for (int n = rows - start - 2; n >= start + 1 && columns - start - 1 > start; n--)
            list.add(matrix[n][start]);
    }
}