[leetcode]Spiral Matrix

新博文地址：[leetcode]Spiral Matrix

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

 这道题是《剑指offer》上的例题，上面的解法很简单，但是我没用，我的算法更简单，而且也是O(m*n)的复杂度，但是需要O(m*n)的空间，当然，也可以不开额外的空间，直接修改原数组。

算法太简单了：

主要就是维护一个visit数组，来标记这个元素是否已经访问过，每圈都是从（0,0）（1,1）这样的（n,n）点开始扫描的，因此startLine表示扫描轮数，startLine <= min(rowCount,columnCount) / 2

不罗嗦了，直接看代码吧。

public List<Integer> spiralOrder(int[][] matrix) {
		List<Integer> list = new ArrayList<Integer>();
		int height = matrix.length;
		if(height == 0) return list;
		int width = matrix[0].length;
		if(width == 1){
			for(int i = 0 ; i < height; list.add(matrix[i][0]),i++);
			return list;
		}
		boolean[][] visited = new boolean[height][width];
		int startLine = 0;
		for(; startLine <= Math.min(height, width) / 2; startLine++){
			for(int i = 0; i < width; i++){
				if(!visited[startLine][i]){
					addToList(matrix, startLine, i, list, visited);
				}
			}
			for(int i = 0 ; i < height; i++){
				if(!visited[i][width - 1 - startLine]){
					addToList(matrix, i,width - 1- startLine, list, visited);
				}
			}
			
			for(int i = width - 1; i >= 0; i--){
				if(!visited[height - 1 - startLine][i]){
					addToList(matrix, height - 1 - startLine, i, list, visited);
				}
			}
			for(int i = height - 1; i >= 0 ; i--){
				if(!visited[i][startLine]){
					addToList(matrix, i,startLine, list, visited);
				}
			}
		}
		return list;
    }
	
	private void addToList(int[][] matrix,int row,int column,List<Integer> list,boolean visited[][]){
		list.add(matrix[row][column]);
		visited[row][column] = true;
	}