【剑指offer】面试题29-顺时针打印矩阵

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.观察每一圈左上角元素的下标，其横纵坐标是相同的，设为(start, start)；
• 2.考虑不同的矩阵形状，我们 假设矩阵的行数为row，列数为col ，可以总结出一个规律，循环执行的条件是row > start * 2 && clo > start * 2 ；
• 3.下面考虑怎样打印每一圈：把打印一圈分成四部分，
  （1）从左到右打印一行：不管形状怎么样，因为是顺时针打印，所以这一步是必须执行的，不需要考虑这一行的元素有多少，直接找到两端遍历打印就可以了；
  （2）从上到下打印一列：如果只有一行，那就不需要执行这一步，所以要执行这一步的条件是起始行号大于起始列号 ；
  （3）从右到左打印一行：如果只有一列，那么这一步不需要执行，所以执行条件是列数不少于2，即终止列号大于起始列号 ；
  （4）从下到上打印一列：如果要执行这一步，那么矩阵至少要有三行两列，因此要求终止行号比起始行号至少大2，同时终止列号要大于起始列号 。

  2. 代码（Java实现）

import java.util.ArrayList;
/**
 * @author : Eleven482-LiQiang
 * @version: 2020年2月16日 上午11:15:03
 */
public class Solution {
	ArrayList<Integer> list = new ArrayList<>();
	public ArrayList<Integer>  printMatrix(int[][] matrix) {

		int start = 0;
		int row = matrix.length;
		int col = matrix[0].length;

		while (col > start * 2 && row > start * 2) {
			PrintMatrixCircle(matrix, col, row, start,list);
			++start;
		}
		return list;
	}

	private void PrintMatrixCircle(int[][] matrix, int col, int row, int start,ArrayList<Integer> list) {
		// TODO Auto-generated method stub
		int endX = col - 1 - start;
		int endY = row - 1 - start;

		// 从左到右打印一行
		for (int i = start; i <= endX; i++) {
			list.add(matrix[start][i]);
			// System.out.print(matrix[start][i] + " ");
		}

		// 从上到下打印一列
		if (start < endY) {
			for (int i = start + 1; i <= endY; i++) {
				list.add(matrix[i][endX]);
				// System.out.print(matrix[i][endX] + " ");
			}
		}

		// 从右到左打印一行
		if (start < endX && start < endY) {
			for (int i = endX - 1; i >= start; i--) {
				list.add(matrix[endY][i]);
				// System.out.print(matrix[endY][i] + " ");
			}
		}

		// 从下到上打印一列
		if (start < endX && start < endY - 1) {
			for (int i = endY - 1; i >= start + 1; i--) {
				list.add(matrix[i][start]);
				// System.out.print(matrix[i][start] + " ");
			}
		}

	}
}

tips：把抽象的问题图形化，往往能更快的找到思路

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/900c1741.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。