`
huntfor
  • 浏览: 194245 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[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;
	}

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics