Problem
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Solution (Java)
class Solution {
public int[][] generateMatrix(int n) {
int num = 1;
int rStart = 0;
int rEnd = n - 1;
int cStart = 0;
int cEnd = n - 1;
int[][] spiral = new int[n][n];
while (rStart <= rEnd && cStart <= cEnd) {
for (int k = cStart; k <= cEnd; k++) {
spiral[rStart][k] = num++;
}
rStart++;
for (int k = rStart; k <= rEnd; k++) {
spiral[k][cEnd] = num++;
}
cEnd--;
if (rStart <= rEnd) {
for (int k = cEnd; k >= cStart; k--) {
spiral[rEnd][k] = num++;
}
}
rEnd--;
if (cStart <= cEnd) {
for (int k = rEnd; k >= rStart; k--) {
spiral[k][cStart] = num++;
}
}
cStart++;
}
return spiral;
}
}
Solution (Javascript)
/**
* @param {number} n
* @return {number[][]}
*/
var generateMatrix = function(n) {
var x1 = 0;
var x2 = n - 1;
var y1 = 0;
var y2 = n - 1;
var i = 0;
var res = Array(n).fill(0).map(_ => Array(n));
while (x1 <= x2 && y1 <= y2) {
for (var x = x1; x <= x2; x++) res[y1][x] = ++i;
for (var y = y1 + 1; y <= y2; y++) res[y][x2] = ++i;
for (var x = x2 - 1; x > x1; x--) res[y2][x] = ++i;
for (var y = y2; y > y1; y--) res[y][x1] = ++i;
x1++;
x2--;
y1++;
y2--;
}
return res;
};
Explain:
绕圈，1 => 2 => 3 => 4 => 5
111
452
432
Complexity:
- Time complexity : O(n^2).
- Space complexity : O(n^2).