|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
- Example 1:
- Input:
- [
- [ 1, 2, 3 ],
- [ 4, 5, 6 ],
- [ 7, 8, 9 ]
- ]
- Output: [1,2,3,6,9,8,7,4,5]
- Example 2:
- Input:
- [
- [1, 2, 3, 4],
- [5, 6, 7, 8],
- [9,10,11,12]
- ]
- Output: [1,2,3,4,8,12,11,10,9,5,6,7]
复制代码
思路:两个pointer,一个横着走,一个竖着走,每次计算matrix 的最外围一周,然后进行递归。考虑特殊情况,一个是empty set,另一个是size one array。
- class Solution {
- public static List<Integer> spiralOrder(int[][] matrix) {
- ArrayList<Integer> recept = new ArrayList<>();
-
- ArrayList<Integer> empty = new ArrayList<Integer>(){};
-
- if(matrix == null || matrix.length == 0){
-
- return empty;
- }
-
- if(matrix.length == 1){
-
- for(int i = 0; i<matrix[0].length; i++ ){
-
- recept.add(matrix[0][i]);
- }
-
- return recept;
- }
- generateList(matrix, recept, matrix[0].length, matrix.length, 0);
- return recept;
- }
- public static void generateList(int[][] matrix, ArrayList<Integer> array, int rowlen, int colen, int n) {
-
- if(matrix == null){
- return;
- }
- int len_of_column = colen - 2*n;
- int len_of_row = rowlen - 2*n;
- if(len_of_column <= 0 || len_of_row <= 0) {
- return;
- }
- int first = 0 + n, second = 0 + n;
- if(first == n) {
- while(first != n+ len_of_row && first>=n && first <= n+ len_of_row) {
- array.add(matrix[0+n][(first++)]);
- // System.out.println(array);
- // System.out.println("-----");
- }
- }
- second++;
- if(first == len_of_row+n && second == n+1) {
- while(second != len_of_column + n && second >=n && second <= len_of_column + n) {
- array.add(matrix[second++][first-1]);
- // System.out.println(array);
- // System.out.println("-----");
- }
- }
- first= first -2 ;
- if(first == len_of_row-2+n && second == len_of_column+n) {
- while(first != 0+n && first >=n && first <= len_of_row+n) {
- array.add(matrix[second-1][(first--)]);
- // System.out.println(array);
- // System.out.println("-----");
- }
- }
- second--;
- if(first == 0+n && second == len_of_column-1+n) {
- while(second != n && second >=n && second <=len_of_column+n) {
- array.add(matrix[(second--)][first]);
- }
- }
- n++;
- generateList(matrix, array, rowlen, colen, n);
- }
- }
复制代码
结果在running time 和 memory usage beat 100% online submissions!!!
|
|