Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: [ [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]
Solution: Simulation
Keep track of the current bounds (left, right, top, bottom).
Init: left = 0, right = n – 1, top = 0, bottom = m – 1
Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public: vector<int> spiralOrder(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int l = 0; int t = 0; int r = matrix[0].size(); int b = matrix.size(); const int total = (r--) * (b--); int d = 0; int x = 0; int y = 0; vector<int> ans; while (ans.size() < total - 1) { if (d == 0) { while (x < r) ans.push_back(matrix[y][x++]); ++t; } else if (d == 1) { while (y < b) ans.push_back(matrix[y++][x]); --r; } else if (d == 2) { while (x > l) ans.push_back(matrix[y][x--]); --b; } else if (d == 3) { while (y > t) ans.push_back(matrix[y--][x]); ++l; } d = (d + 1) % 4; } if (ans.size() != total) ans.push_back(matrix[y][x]); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment