2014年4月16日 星期三

[LeetCode] Spiral Matrix

Problem:
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].
Solution: O(mn)
public class Solution {
    public ArrayList spiralOrder(int[][] matrix) {
        ArrayList list = new ArrayList();
        if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
         return list;
        int way = 1;//(0,1) (1,0)  (0,-1)  (-1,0)       1 right 2 down 3 left 4 up
        int x = 0; 
        int y = 0;
        while(list.size() != matrix.length* matrix[0].length){
            if(way == 1){
                if(y == matrix[0].length){
                    y--;
                    x++;
                    way = 2;
                }
                else if(list.contains(matrix[x][y])){
                    way = 2;
                    y--;
                    x++;
                }else{
                    list.add(matrix[x][y]);
                    y++;
                }
            }
            else if(way == 2){
                if(x == matrix.length){
                    x--;
                    y--;
                    way = 3;
                }
                else if(list.contains(matrix[x][y])){
                    way = 3;
                    y--;
                    x--;
                }else{
                    list.add(matrix[x][y]);
                    x++;
                }
            }
            else if(way == 3){
                if(y == -1){
                    y++;
                    way = 4;
                    x--;
                }
                else if(list.contains(matrix[x][y])){
                    way = 4;
                    x--;
                    y++;
                }else{
                    list.add(matrix[x][y]);
                    y--;
                }
            }
            else{
                if(list.contains(matrix[x][y])){
                    way = 1;
                    x++;
                    y++;
                }else{
                    list.add(matrix[x][y]);
                    x--;
                }
            }
        }
        return list;
    }
}

沒有留言:

張貼留言