[LeetCode]Spiral Matrix

Question
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]​​.

本题难度Medium。

顺序添加法

【复杂度】
时间 O(MN) 空间 O(1)

【思路】
首先考虑最简单的情况，如图我们先找最外面这圈X，这种情况下我们是第一行找前4个，最后一列找前4个，最后一行找后4个，第一列找后4个，这里我们可以发现，第一行和最后一行，第一列和最后一列都是有对应关系的。即对​​​i​​​行，其对应行是​​m - i - 1​​​，对于第​​j​​​列，其对应的最后一列是​​n - j - 1​​。

XXXXX
XOOOX
XOOOX
XOOOX
XXXXX

然后进入到里面那一圈，同样的顺序没什么问题，然而关键在于下图这么两种情况，一圈已经没有四条边了，所以我们要单独处理，只加那唯一的一行或一列。另外，根据下图我们可以发现，圈数是宽和高中较小的那个，加1再除以2。

OOOOO  OOO
OXXXO  OXO
OOOOO  OXO
       OXO
       OOO

【注意】
7-10行不要写成：

int m=matrix.length,n=matrix[0].length;

它对于测试用例​​matrix=[]​​会出现 out of bounds exception 错误。

【代码】

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        //require
        List<Integer> ans=new ArrayList<Integer>();
        if(matrix==null)
            return ans;
        int m=matrix.length;
        if(m<1)
            return ans;
        int n=matrix[0].length;
        //count the cylinder number
        int cycle=(Math.min(m, n) + 1) / 2;
        int r=0,c=0;
        //invariant
        for(int i=0;i<cycle;i++){
            int lastRow=m-r-1;
            int lastCol=n-c-1;
            if(r==lastRow){
                for(int j=c;j<=lastCol;j++)
                    ans.add(matrix[r][j]);
            }else if(c==lastCol){
                for(int j=r;j<=lastRow;j++)
                    ans.add(matrix[j][c]);
            }else{
                for(int j=c;j<lastCol;j++)
                    ans.add(matrix[r][j]);
                for(int j=r;j<lastRow;j++)
                    ans.add(matrix[j][lastCol]);
                for(int j=lastCol;j>c;j--)
                    ans.add(matrix[lastRow][j]);
                for(int j=lastRow;j>r;j--)
                    ans.add(matrix[j][c]);
                r++;c++;
            }
        }
        //ensure
        return ans;
    }

}

【附】
更好的代码参考：​​Spiral Matrix I​​
他没有使用变量​​​r​​​、​​c​​。

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<Integer>();
        if(matrix.length == 0) return res;
        int m = matrix.length, n = matrix[0].length;
        // 计算圈数
        int lvl = (Math.min(m, n) + 1) / 2;
        for(int i = 0; i < lvl; i++){
            // 计算相对应的该圈最后一行
            int lastRow = m - i - 1;
            // 计算相对应的该圈最后一列
            int lastCol = n - i - 1;
            // 如果该圈第一行就是最后一行，说明只剩下一行
            if(i == lastRow){
                for(int j = i; j <= lastCol; j++){
                    res.add(matrix[i][j]);
                }
            // 如果该圈第一列就是最后一列，说明只剩下一列
            } else if(i == lastCol){
                for(int j = i; j <= lastRow; j++){
                    res.add(matrix[j][i]);
                }
            } else {
                // 第一行
                for(int j = i; j < lastCol; j++){
                    res.add(matrix[i][j]);
                }
                // 最后一列
                for(int j = i; j < lastRow; j++){
                    res.add(matrix[j][lastCol]);
                }
                // 最后一行
                for(int j = lastCol; j > i; j--){
                    res.add(matrix[lastRow][j]);
                }
                // 第一列
                for(int j = lastRow; j > i; j--){
                    res.add(matrix[j][i]);
                }
            }
        }
        return res;
    }
}

参考

​​Spiral Matrix I​​