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. // LeetCode, Spiral Matrix
  2. // @author 龚陆安 (http://weibo.com/luangong)
  3. // 时间复杂度O(n^2)，空间复杂度O(1)
  4. class Solution {
  5. public:
  6.     vector<int> spiralOrder(vector<vector<int> >& matrix) {
  7.         vector<int> result;
  8.         if (matrix.empty()) return result;
  9.         int beginX = 0, endX = matrix[0].size() - 1;
  10.         int beginY = 0, endY = matrix.size() - 1;
  11.         while (true) {
  12.             // From left to right
  13.             for (int j = beginX; j <= endX; ++j) result.push_back(matrix[beginY][j]);
  14.             if (++beginY > endY) break;
  15.             // From top to bottom
  16.             for (int i = beginY; i <= endY; ++i) result.push_back(matrix[i][endX]);
  17.             if (beginX > --endX) break;
  18.             // From right to left
  19.             for (int j = endX; j >= beginX; --j) result.push_back(matrix[endY][j]);
  20.             if (beginY > --endY) break;
  21.             // From bottom to top
  22.             for (int i = endY; i >= beginY; --i) result.push_back(matrix[i][beginX]);
  23.             if (++beginX > endX) break;
  24.         }
  25.         return result;
  26.     }
  27. };

解法2 递归

相关题目

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