54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

---

package leetCode5_26;

import java.util.ArrayList;
import java.util.List;

/** 
* @author : caoguotao
* @date 创建时间：2019年6月2日 下午9:29:07 
* @version 1.0 
* @parameter  
* @since  
* @return  
*/
/**
 * 思路：计算层数
 * 	         从上-》右-》下-》左依次遍历
 * 	         注意重复输出
 * 思路2：计算层数
 * 	         从上-》右-》下-》左依次遍历,将遍历过的位置标记为已遍历，可以避免重复遍历
 * @author 16213
 *
 */
public class Solution54 {

	public static void main(String[] args) {
		Solution54 s = new Solution54();
		int[][] matrix = {
				{1,11},{2,12},{3,13},{4,14},
				{5,15},{6,16},{7,17},{8,18},
				{9,19},{10,20}
		};
		List<Integer> res = s.spiralOrder(matrix);
		for (Integer integer : res) {
			System.out.print(integer +" ");
		}
	}
	/**
	 * 	顺时针旋转数组
	 * @param matrix 原二维数组
	 * @return	顺时针旋转之后的list
	 */
	public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> list = new ArrayList<Integer>();
		//行、列
		int rows = matrix.length;
		if(rows == 0) {
			return list;
		}
		int cols = matrix[0].length;
		//计算层数
		int layers = (Math.min(rows, cols) + 1) / 2;
		for(int i = 0; i < layers; i++) {
			//每一圈列的个数
			int col = cols - 2 * i;
			//输出最上一行
			for(int j = i; j < col + i; j++) {
				list.add(matrix[i][j]);
			}
			//输出右边一列
			for(int k = i + 1 ; k < rows - i; k++) {
				list.add(matrix[k][cols - 1 - i]);
			}
			//输出最下一行
			for(int l = cols - 2 - i; l > i; l--) {
				list.add(matrix[rows - 1 - i][l]);
			}
			//输出左边一列
			for(int m = rows - 1 - i; m > i; m--) {
				//避免在只剩一列的时候与最右一列重复输出
				if(i == cols- i - 1) {
					
				}else {
					list.add(matrix[m][i]);
				}	
			}
		}
		return list;
	}
}