Spiral Matrix 374

Question

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

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

Solution

一圈一圈（上－>右->下->左）输出matrix。每一轮消耗2层row和2层column。边界情况为到达最内层时，若row或者column为偶数，则和之前一样输出；若row或者column为奇数，则最内层只剩下一行或者一列，只要输出此时的上->右即可。

代码如下：

Non-Recuresion:

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> rst = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0) 
            return rst;

        int rows = matrix.length;
        int cols = matrix[0].length;
        int count = 0;
        while(count * 2 < rows && count * 2 < cols){
            for(int i = count; i < cols-count; i++)
                rst.add(matrix[count][i]);


            for(int i = count+1; i< rows-count; i++)
                rst.add(matrix[i][cols-count-1]);

            if(rows - 2 * count == 1 || cols - 2 * count == 1)  // if only one row /col remains
                break;

            for(int i = cols-count-2; i>=count; i--)
                rst.add(matrix[rows-count-1][i]);

            for(int i = rows-count-2; i>= count+1; i--)
                rst.add(matrix[i][count]);

            count++;
        }
        return rst;
    }
}

Recursion:

public class Solution {
    /**
     * @param matrix a matrix of m x n elements
     * @return an integer list
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // Write your code here
        List<Integer> result = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return result;
        }

        int row = matrix.length;
        int col = matrix[0].length;

        Helper(matrix, 0, row, col, result);
        return result;
    }

    private void Helper(int[][] matrix, int distance, int row, int col, List<Integer> result){
        //row或column为偶数
        if(row - distance * 2 == 0 || col - distance * 2 == 0){
            return;
        }

        //只剩一行
        if(row - distance * 2 == 1){
            for(int j = distance; j <= col - 1 - distance; j++){
                result.add(matrix[distance][j]);
            }
            return;
        }
        //只剩一列
        if(col - distance * 2 == 1){
            for(int i = distance; i <= row - 1 - distance; i++){
                result.add(matrix[i][distance]);
            }
            return;
        }
        //上
        for(int j = distance; j <= col - 1 - distance; j++){
            result.add(matrix[distance][j]);
        }
        //右
        for(int i = distance + 1; i <= row - 2 - distance; i++){
            result.add(matrix[i][col - 1 - distance]);
        }
        //下
        for(int j = col - 1 - distance; j >= distance; j--){
            result.add(matrix[row - 1 - distance][j]);
        }
        //左
        for(int i = row - 2 - distance; i >= distance + 1; i--){
            result.add(matrix[i][distance]);
        }

        Helper(matrix, distance + 1, row, col, result);
    }
}