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

这道题我的思路就是一圈一圈的recursive求,记录每圈的m和n,还有开始的坐标,如果只剩一行/一列要单独处理,如果m, n小于或等于0的话就直接return一个空集,处理完一圈以后,recursive求剩下的所有圈的spirialMatrix然后append到自己这一圈上再返回给上一层即可。

public class Solution
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return (new ArrayList<Integer>());
        }
        int n = matrix[0].length;
        return oneSpirialCircle(matrix, m, n, 0, 0);
    }
    
    public ArrayList<Integer> oneSpirialCircle(int [][] matrix, int m, int n, int r, int c) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (m <= 0 || n <= 0 )
            return res;
        if (m == 1)
        {
            for(int i = c; i < c+n; i++)
            {
                res.add(matrix[r][i]);
            }
            return res;
        }
        if ( n == 1)
        {
            for (int i = r; i < r + m; i++) {
                res.add(matrix[i][c]);
            }
            return res;
        }
        for(int i = c; i < c + n - 1; i++)
        {
            res.add(matrix[r][i]);
        }
        for (int i = r; i < r+m-1; i++)
        {
            res.add(matrix[i][c+n-1]);
        }
        for (int i = c + n - 1; i > c; i--)
        {
            res.add(matrix[r+m-1][i]);
        }
        for (int i = r+m-1; i > r; i--)
        {
            res.add(matrix[i][c]);
        }
        ArrayList<Integer> next = oneSpirialCircle(matrix, m-2, n-2, r+1, c+1);
        if (!next.isEmpty())
        {
            res.addAll(next);
        }
        return res;
    }
    
}

Second Submission without recursion: The problem here is how to deal with the last row/col, if there is one row left, we do scan left from right, if is one col, we scan top to bottom, using 4 instead of 2 markers to make thing more clear.

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (matrix.length == 0)
            return res;
        int m = matrix.length;
        int n = matrix[0].length;
        int startCol = 0;
        int endCol = n-1;
        int startRow = 0;
        int endRow = m-1;
        while(startRow < endRow && startCol < endCol) {
            for (int i = startCol; i < endCol; i++) {
                res.add(matrix[startRow][i]);
            }
            for (int i = startRow; i < endRow; i++) {
                res.add(matrix[i][endCol]);
            }
            for (int i = endCol; i > startCol; i--) {
                res.add(matrix[endRow][i]);
            }
            for (int i = endRow; i > startRow; i--) {
                res.add(matrix[i][startCol]);
            }
            startRow++;
            endRow--;
            startCol++;
            endCol--;
        }
        if (startRow == endRow) {//last row
            for (int i = startCol; i <= endCol; i++)
                res.add(matrix[startRow][i]);
        }
        else if (startCol == endCol) {//last col
            for (int i = startRow; i <= endRow; i++)
                res.add(matrix[i][startCol]);
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s