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:
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 ArrayListspiralOrder(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; } }
沒有留言:
張貼留言