首页 > 代码库 > 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(螺旋矩阵)