【Java】面试题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。

思路：
首先拿到这个题，读完题我们脑子里会呈现出这样的一个画面。从外圈到内圈顺序的依次打印，我们就可以把矩阵想象成若干个圈，如上图所示，我们可以用一个循环来打印矩阵，每一次打印矩阵中的一个圈。那么循环结束的条件是什么？假设这个矩阵的行数是rows，列数是columns。打印第一圈的左上角的坐标是（0, 0），第二圈的左上角的坐标是（1, 1），依次类推。我们注意到左上角的坐标中行标和列标总是相同的，于是可以在矩阵中选取左上角为（start，start）的一圈作为我们的分析的目标。

对于一个5*5的矩阵，最后一圈只有一个数字，对应的坐标为（2, 2）。5 > 2 * 2；

对于一个6*6的矩阵，最后一圈有4个数字，其左上角的坐标仍是（2, 2）。6 > 2 *2；

故循环继续的条件为columns > startX * 2并且rows > startY * 2。

打印一圈的实现可以分为4步：第一步从左到右打印一行，第二步从上到下打印一列，第三步从右到左打印一行，第四步从下到上打印一列（每一步根据起始坐标和终止坐标用一个循环就能打印出一行或者一列）。
注意：最后一圈可能退化成只有一行、只有一列，甚至只有一个数字，因此打印这样的一圈就不再需要四步，可能只需要三步、两步、一步。

接下来我们分析打印时每一步的前提条件。第一步总是需要的，因为打印一圈至少有一步。如果只有一行，那么就不用第二步了。即第二步的前提条件是终止行号大于起始行号。打印第三步的前提条件是圈内至少有两行两列。即除了要求终止行号大于起始行号外，还需要终止列号大于起始列号。同理打印第四步的前提条件是至少有三行两列，即要求终止行号比起始行号至少大2，同时终止列号大于起始列号。

代码实现：

package jianZhiOffer;

import java.util.ArrayList;

/*
 * 面试题29：顺时针打印矩阵
 * 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
 */
public class Demo29 {
	public static void main(String[] args) {
		int[][] num= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
		System.out.print(printMatrixClockwisely(num));
		System.out.print(" ");

	}
	
	public static ArrayList<Integer> printMatrixClockwisely(int[][] nums){
		ArrayList<Integer> list = new ArrayList<Integer>();
		int rows=nums.length;
		int cols=nums[0].length;
		if(nums==null || cols<=0 || rows<=0) {
			return null;
		}
		int start=0;
		while(cols>start*2 && rows>start*2) {
			printMatrixInCircle(list,nums,cols,rows,start);
			start++;
		}
		return list;
	}
	
	private static void printMatrixInCircle(ArrayList<Integer>list, 
			int[][] nums,int cols,int rows,int start) {
		int endX = cols-1-start;
		int endY = rows-1-start;
		
		//从左到右打印一行
		for(int i=start;i<=endX;i++) {
			int number = nums[start][i];
			list.add(number);
		}
		
		//从上到下打印一列
		if(start<endY) {  //终止行号大于起始行号
			for(int i=start+1;i<=endY;i++) {
				int number=nums[i][endX];
				list.add(number);
			}
		}
		
		//从右到左打印一行
		if(start<endX && start<endY) {  //终止行号大于起始行号，终止列号大于起始列号
			for(int i=endX-1;i>=start;i--) {
				int number=nums[endY][i];
				list.add(number);
			}
		}
		
		//从下向上打印一列
		if(start<endX && start<endY-1) { //终止列号大于起始列号，终止行号比起始行号至少大2
			for(int i=endY-1;i>=start+1;i--) {
				int number=nums[i][start];
				list.add(number);
			}
		}
	}

}