Spiral Matrix II

描述

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

For example,Given n = 3,

You should return the following matrix:

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

分析

这题比上一题要简单。

代码1

  1. // Spiral Matrix II
  2. // 时间复杂度O(n^2)，空间复杂度O(n^2)
  3. class Solution {
  4. public:
  5.     vector > generateMatrix(int n) {
  6.         vector > matrix(n, vector(n));
  7.         int begin = 0, end = n - 1;
  8.         int num = 1;
  10.         while (begin < end) {
  11.             for (int j = begin; j < end; ++j) matrix[begin][j] = num++;
  12.             for (int i = begin; i < end; ++i) matrix[i][end] = num++;
  13.             for (int j = end; j > begin; --j) matrix[end][j] = num++;
  14.             for (int i = end; i > begin; --i) matrix[i][begin] = num++;
  15.             ++begin;
  16.             --end;
  17.         }
  19.         if (begin == end) matrix[begin][begin] = num;
  21.         return matrix;
  22.     }
  23. };

代码2

  1. // LeetCode, Spiral Matrix II
  2. // @author 龚陆安 (http://weibo.com/luangong)
  3. // 时间复杂度O(n^2)，空间复杂度O(n^2)
  4. class Solution {
  5. public:
  6.     vector<vector<int> > generateMatrix(int n) {
  7.         vector< vector<int> > matrix(n, vector<int>(n));
  8.         if (n == 0) return matrix;
  9.         int beginX = 0, endX = n - 1;
  10.         int beginY = 0, endY = n - 1;
  11.         int num = 1;
  12.         while (true) {
  13.             for (int j = beginX; j <= endX; ++j) matrix[beginY][j] = num++;
  14.             if (++beginY > endY) break;
  16.             for (int i = beginY; i <= endY; ++i) matrix[i][endX] = num++;
  17.             if (beginX > --endX) break;
  19.             for (int j = endX; j >= beginX; --j) matrix[endY][j] = num++;
  20.             if (beginY > --endY) break;
  22.             for (int i = endY; i >= beginY; --i) matrix[i][beginX] = num++;
  23.             if (++beginX > endX) break;
  24.         }
  25.         return matrix;
  26.     }
  27. };

相关题目

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