首页 > 代码库 > LeetCode 54. Spiral Matrix(螺旋矩阵)
LeetCode 54. 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 ] ]
You should return [1,2,3,6,9,8,7,4,5]
.
题目标签:Array
这道题目给了我们一个矩阵,m*n,让我们返回一个螺旋矩阵排列的array,这题目名字听着挺酷炫呀。我们来看原题例子:
1 2 3
4 5 6
7 8 9
一共有4步骤:我们还需要设置rowBegin = 0, rowEnd = 2, colBegin = 0, colEnd = 2.
1. 红色:从rowBegin这一排向右遍历,加入每一个matrix[rowBegin][j], j: colBegin ~ colEnd. 遍历完要把rowBegin++, 从下一排继续;
2. 绿色:从colEnd这一列开始向下遍历,加入每一个matrix[j][colEnd], j: rowBegin ~ rowEnd. 遍历完要把colEnd--, 从左边那列继续;
3. 蓝色:从rowEnd这一排向左遍历,加入每一个matrix[rowEnd][j], j: colEnd ~ colBegin. 遍历完要把rowEnd--, 从上一排继续。
4. 灰色:从colBegin这一列开始向上遍历,加入每一个matrix[j][colBegin], j: rowEnd ~ rowBegin, 遍历完要把colBegin++, 从右边那列继续。
那什么时候要结束呢,可以利用m*n 得到一共的数量,每次加入一个,就把这个数量-1, 当数量等于0的时候意味着我们加完了所有的数字,return res 就可以了。
Java Solution:
Runtime beats 20.42%
完成日期:07/18/2017
关键词:Array
关键点:螺旋矩阵的固定模式
1 public class Solution 2 { 3 public List<Integer> spiralOrder(int[][] matrix) 4 { 5 List<Integer> res = new ArrayList<Integer>(); 6 7 if(matrix.length == 0) 8 return res; 9 10 int totalNum = matrix.length * matrix[0].length; 11 12 int rowBegin = 0; 13 int rowEnd = matrix.length - 1; 14 int colBegin = 0; 15 int colEnd = matrix[0].length - 1; 16 17 while(totalNum > 0) 18 { 19 // traverse right 20 for(int j=colBegin; j<=colEnd && totalNum>0; j++) 21 { 22 res.add(matrix[rowBegin][j]); 23 totalNum--; 24 } 25 rowBegin++; 26 27 // traverse Down 28 for(int j=rowBegin; j<=rowEnd && totalNum>0; j++) 29 { 30 res.add(matrix[j][colEnd]); 31 totalNum--; 32 } 33 colEnd--; 34 35 // traverse left 36 for(int j=colEnd; j>=colBegin && totalNum>0; j--) 37 { 38 res.add(matrix[rowEnd][j]); 39 totalNum--; 40 } 41 rowEnd--; 42 43 // traverse up 44 for(int j=rowEnd; j>= rowBegin && totalNum>0; j--) 45 { 46 res.add(matrix[j][colBegin]); 47 totalNum--; 48 } 49 colBegin++; 50 } 51 52 return res; 53 54 } 55 }
参考资料:
https://leetcode.com/problems/spiral-matrix/#/discuss
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 54. Spiral Matrix(螺旋矩阵)