Description
Given an m x n
matrix
, return all elements of the matrix
in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[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]
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Code
Time Complexity: , Space Complexity:
關鍵就是觀察規律:
vector<vector<int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while(directionalSteps[dir_idx % 2])
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<vector<int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<int> answer;
int m = matrix.size(), n = matrix[0].size();
if (m == 0 || n == 0) return answer;
vector<int> directionalSteps = {n, m - 1};
int dir_idx = 0;
int i = 0, j = -1;
while(directionalSteps[dir_idx % 2]){
for(int k = 0; k < directionalSteps[dir_idx % 2]; k++) {
i += dir[dir_idx][0];
j += dir[dir_idx][1];
answer.push_back(matrix[i][j]);
}
directionalSteps[dir_idx % 2]--;
dir_idx = (dir_idx + 1) % 4;
}
return answer;
}
};