剑指offer面试题29:顺时针打印矩阵（Java实现）

78 阅读 0 评论 52 点赞

我是靠谱客的博主成就玫瑰，最近开发中收集的这篇文章主要介绍剑指offer面试题29:顺时针打印矩阵（Java实现），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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.

先上代码:

import java.util.ArrayList;

public class PrintMatrixClockwisely {
	public static void main(String[] args) {
		// 方便测试，我们就在主方法里面进行添加需要进行测试的数据；
		int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };
		// 为了满足不同需求，可能面试官不仅仅让你打印出来，可能让你将打印顺序用保存起来.我们这里使用ArrayList保存数据

		ArrayList<Integer> result = new ArrayList<>(); // 初始化数据
		result = printJudgeCircxle(matrix);

		System.out.println("------------");
		// 将结果打印，检验正确性:
		for (int i = 0; i < result.size(); i++) {
			System.out.print(result.get(i) + ",");
		}
	}

	private static ArrayList<Integer> printJudgeCircxle(int[][] matrix) {
		ArrayList<Integer> result = new ArrayList<>();
		// 做好边缘测试
		if (matrix == null)
			return result;
		if (matrix.length == 0 || matrix[0].length == 0)
			return result;

		int start = 0; //检验是否需要进行打印当前，判断方法下面解析介绍
		while (start * 2 < matrix.length && start * 2 < matrix[0].length) {
			result = printCircle(matrix, matrix.length, matrix[0].length, start, result);
			start++;
		}
		return result;
	}

	private static ArrayList<Integer> printCircle(int[][] matrix, int rows, int columns, int start,     
			ArrayList<Integer> result) {
		int endX = columns - start - 1;  //结尾X
		int endY = rows - start - 1;  //结尾Y
		// 首先是从左到右打印。
		for (int i = start; i <= endX; i++) {
			System.out.print(matrix[start][i] + ",");
			result.add(matrix[start][i]);
		}

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

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

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

分析：

我们打印一个矩阵按照顺时针方向，经过观察我们发现在打印的过程中，实际上是在打印圈，一圈一圈的打印。我们可以利用一个循环来打印矩阵。

接下来分析，是如何判断循环条件，假设这个矩阵的行数是rows，列数是column。打印第一圈的坐上角的坐标是（0，0），第二圈的左上角坐标是（1，1），以此类推。我们注意到，左上角的行坐标和列坐标总是相同的，于是可以用左上角的（start，start）来作为一圈的目标。

对于一个5X5的矩阵，最有一圈只有一个数字，对应的坐标是（2，2）我们发现5>2x2。对于一个6X6的矩阵，最后一圈有4个数字，我们发信6>2X2依然成立。因此得出循环的必要条件是columns>start*2 && rows>start*2


		int start = 0; //检验是否需要进行打印当前，判断介绍
		while (start * 2 < matrix.length && start * 2 < matrix[0].length) {
			result = printCircle(matrix, matrix.length, matrix[0].length, start, result);
			start++;
		}

在打印一圈的过程中，可能出现四种情况，我们要逐一进行分析。其中endY表示中止行号，endX表示中止列号

1）退化成一步：第一步从左向右打印每一步都会经历，它总是需要的。