Spiral Matrix

描述

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

For example,Given the following matrix:

  1. [
  2.  [ 1, 2, 3 ],
  3.  [ 4, 5, 6 ],
  4.  [ 7, 8, 9 ]
  5. ]

You should return [1,2,3,6,9,8,7,4,5].

分析

模拟。

解法1 迭代

  1. // Spiral Matrix
  2. // 时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<Integer> spiralOrder(int[][] matrix) {
  5.         List<Integer> result = new ArrayList<>();
  6.         if (matrix.length == 0) return result;
  7.         int beginX = 0, endX = matrix[0].length - 1;
  8.         int beginY = 0, endY = matrix.length - 1;
  9.         while (true) {
  10.             // From left to right
  11.             for (int j = beginX; j <= endX; ++j) result.add(matrix[beginY][j]);
  12.             if (++beginY > endY) break;
  13.             // From top to bottom
  14.             for (int i = beginY; i <= endY; ++i) result.add(matrix[i][endX]);
  15.             if (beginX > --endX) break;
  16.             // From right to left
  17.             for (int j = endX; j >= beginX; --j) result.add(matrix[endY][j]);
  18.             if (beginY > --endY) break;
  19.             // From bottom to top
  20.             for (int i = endY; i >= beginY; --i) result.add(matrix[i][beginX]);
  21.             if (++beginX > endX) break;
  22.         }
  23.         return result;
  24.     }
  25. }

解法2 递归

  1. // Spiral Matrix
  2. // 时间复杂度O(n^2)，空间复杂度O(1)
  3. public class Solution {
  4.     public List<Integer> spiralOrder(int[][] matrix) {
  5.         List<Integer> result = new ArrayList<>();
  6.         if (matrix.length == 0) return result;
  8.         left = 0;
  9.         right = matrix[0].length - 1;
  10.         up = 0;
  11.         down = matrix.length - 1;
  12.         dfs(matrix, 0, 0, 0, result);
  13.         return result;
  14.     }
  16.     private void dfs(int[][] matrix, int i, int j, int direction,
  17.                      List<Integer> result) {
  18.         if (i < up || i > down) return;
  19.         if (j < left || j > right) return;
  20.         result.add(matrix[i][j]);
  22.         int nextDirection = (direction + 1) % 4;
  23.         switch (direction) {
  24.             case 0:  // right
  25.                 if (j < right) {
  26.                     dfs(matrix, i, j + 1, direction, result);
  27.                 } else {
  28.                     ++up;
  29.                     dfs(matrix, i + 1, j, nextDirection, result);
  30.                 }
  31.                 break;
  32.             case 1:  // down
  33.                 if (i < down) {
  34.                     dfs(matrix, i+1, j, direction, result);
  35.                 } else {
  36.                     --right;
  37.                     dfs(matrix, i, j - 1, nextDirection, result);
  38.                 }
  39.                 break;
  40.             case 2:  // left
  41.                 if (j > left) {
  42.                     dfs(matrix, i, j - 1, direction, result);
  43.                 } else {
  44.                     --down;
  45.                     dfs(matrix, i - 1, j, nextDirection, result);
  46.                 }
  47.                 break;
  48.             default: // up
  49.                 if (i > up) {
  50.                     dfs(matrix, i - 1, j, direction, result);
  51.                 } else {
  52.                     ++left;
  53.                     dfs(matrix, i, j + 1, nextDirection, result);
  54.                 }
  55.         }
  57.     }
  59.     private int left;
  60.     private int right;
  61.     private int up;
  62.     private int down;
  63. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/simulation/spiral-matrix.html